A question about calculating visibilty

SGDK only sub forum

Moderator: Stef

Post Reply
themrcul
Very interested
Posts: 116
Joined: Fri Apr 15, 2016 2:21 pm

A question about calculating visibilty

Post by themrcul » Sun Apr 30, 2017 9:55 am

Hi all,

I have a question to you all about how you manage which sprites are visible or not in a map.

I am building an engine before a game, and while I have an idea of the next game I want to make and it's needs, I am trying to make the engine flexible for my next project as well.

The first game will likely be mostly side-scrolling, so checks to see when to bring a sprite onto the screen is a bit simpler - the solution I have made in my head is to:
1) In the editor before export, arrange all static (non-moving) objects in X order ascending.
2) In Engine, when map is loaded make runtime list of all static objects that are in map, with two indexes, one for the last visible object to the left of the screen (lets call it screenLeftStaticObjectIndex, and one for the last visible object to the right of the screen (lets call it screenRightStaticObjectIndex).

3) If the camera moves to the right, look through the list of static objects starting from screenRightStaticObjectIndex, and for each object, until we get to an object that is not visible (at which point we break out of the loop) - allocate hardware sprites, and copy it's tiles into VRAM, incrementing screenRightStaticObjectIndex each time we add an object on screen.
Moving the camera to the left is the reverse, and should be self-explanatory.

Moving objects would need their own checks each time they or the camera moves.

--

This works at least in my head, and should minimise the number of conditionals running each update.

The problem is for a more top-down camera game, with large maps.
I thought of extending my code logic to include the Y axis, but there could be many checks before it gets to the next invisible X object to break out of the loop with, and may well not be performant.

How are people doing object visibility checks in your games? Particularly for levels with lots of height and/or top-down games with large maps?

djcouchycouch
Very interested
Posts: 710
Joined: Sat Feb 18, 2012 2:44 am

Re: A question about calculating visibilty

Post by djcouchycouch » Sun Apr 30, 2017 11:54 am

Sounds like a good start.

Because you can go back and forth, when preparing to spawn an object you'll have to add an extra check to see that the object doesn't exist already.

Goplanes had just a few enemies in a level, so I just kept them in memory and only updating them if the were close enough to the player. Even then the engine could support 80 or 100 objects so it could've done more as it was fast enough.

ViolencePingouin, which I've looked at for the first time in years, seems to break a level into sections. Each section has a collection of objects to spawn. I don't remember the thinking behind it, but you could use that if you're doing an 8-way scrolling game. Break your level out into rectangular areas and then spawn/despawn those sections while moving around.

themrcul
Very interested
Posts: 116
Joined: Fri Apr 15, 2016 2:21 pm

Re: A question about calculating visibilty

Post by themrcul » Sun Apr 30, 2017 11:50 pm

Thanks DJ,

With your Goplanes implementation, you mention you only update the objects that are close to the player.
How are you determining when to update them?
* Are you checking each frame whether they are visible and therefore whether they need to be updated?
* Are you checking only if the camera has moved (but still for each move)?
* Or are you using some other method to cull the list of checks to do each frame?

For now perhaps I'll allow two implementations, and the scheme for determining whether sprites are brought into the scene or not is based on which option is chosen for that map - horizontal only implementation, or "areas" based implementation - where the user needs to divide the map up into areas. If the camera enters an area, all sprites are allocated and are used as the pool of objects to check visibility with. When the camera leaves an area, the sprites in that list are deallocated and are therefore not checked.
The editor program will need to be made a bit more sophisticated for that to work, but I was already thinking of making such a system for changing tilesets in large maps to add variety to a large map as the camera scrolls around, and even palette changes as well. Perhaps a generic "area manager" system can be created, which could include static sprites as well.

For now, since the first game I aim to build is mainly a side scroller, I might get away with just the first implementation (which will be a lot simpler in both the editor and engine and likely runtime speed).
If/when I move on to a top-down RPG style game, then the area based approach will need to be made.

Thanks for your reply again DJ, it has helped solidify my ideas on how to approach this problem!

djcouchycouch
Very interested
Posts: 710
Joined: Sat Feb 18, 2012 2:44 am

Re: A question about calculating visibilty

Post by djcouchycouch » Mon May 01, 2017 2:39 am

themrcul wrote:Thanks DJ,
How are you determining when to update them?
* Are you checking each frame whether they are visible and therefore whether they need to be updated?
* Are you checking only if the camera has moved (but still for each move)?
* Or are you using some other method to cull the list of checks to do each frame?
Memory is fuzzy, but I think:

- yes, it checks all the objects in the world each frame
- the plane in Goplanes moved all the time so no
- the visibility check was bigger than the screen. I think it was maybe four screens around the player.

The CPU was fast enough to do all this reasonably fast, so I didn't feel that I had to optimize it.

themrcul
Very interested
Posts: 116
Joined: Fri Apr 15, 2016 2:21 pm

Re: A question about calculating visibilty

Post by themrcul » Mon May 01, 2017 2:59 am

Interesting, perhaps I am underestimating the power of Blast Processing!
I heard that SGDK's internal SpriteEngine had performance issues dealing with more than 5 or 6 multi-sprites on the screen at once so I was approaching the writing of my Sprite Engine extremely carefully.

It's still good to be careful of course, but maybe I don't have to worry about it so much at this stage, thanks again DJ!

Edit: wording

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: A question about calculating visibilty

Post by Stef » Tue May 02, 2017 9:11 am

The last version of SGDK offers better performance on the sprite engine, you should be able to handle more than 10 visible sprites without speed issues but still the code is in C and can be improved by using assembly on critical parts. Another problem of the SGDK sprite engine is that it has be made to be really flexible which has a cost on the performance... You can use dynamic or static resource allocation, use auto or manual visibility computing.. the more things static / manual, the more performance you get :)

themrcul
Very interested
Posts: 116
Joined: Fri Apr 15, 2016 2:21 pm

Re: A question about calculating visibilty

Post by themrcul » Tue May 02, 2017 9:57 am

Ah ok, thanks Stef for that info. It's great to know it has better performance now!

I really do like your implementation and it's flexibility.
But it's also fun to design my own, and hopefully it will be more specific to the needs of this project too.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: A question about calculating visibilty

Post by Miquel » Mon May 29, 2017 12:30 pm

themrcul wrote: The problem is for a more top-down camera game, with large maps.
I thought of extending my code logic to include the Y axis, but there could be many checks before it gets to the next invisible X object to break out of the loop with, and may well not be performant.
I think you thought is hard to beat.
For example, let's suppose the playfield is 1024x1024 pixels in size, and in this frame the player has move 5 pixels to the right (quite a lot in fact), you have to check for spawn spots on an area of 5x1024 pixels. It's not so big! with the most probability you will hit 0 spawn spots.
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: A question about calculating visibilty

Post by Sik » Mon May 29, 2017 6:55 pm

For the record, I think the problem is not so much that but rather how to store the data in ROM in a reasonable amount of space while still making it fast to traverse.
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: A question about calculating visibilty

Post by Miquel » Mon May 29, 2017 11:33 pm

All you need is an array with the minimun data being: the x,y coordinates and the id of the object/entity/sprite to spawn. In two games I coded that use this feature I also include width, height and a few flags to work with events and triggers. In truth is a more abstract structure used for a few more similar propouses.
Miquel wrote:I think you thought is hard to beat.
For example, let's suppose the playfield is 1024x1024 pixels in size, and in this frame the player has move 5 pixels to the right (quite a lot in fact), you have to check for spawn spots on an area of 5x1024 pixels. It's not so big! with the most probability you will hit 0 spawn spots.
On the other hand if you move verticaly you need to cheeck an area of 320x1024, wich will hit in average a few spawn points. An optimization could be to be prepared to sort with x and y coordinates and use the most convenient of the two.

To me, more than a performance issue, is a design question: ¿do you want sprites to respawn, to reset their locations, or not? An advise, common sense could be tricky here.
Last edited by Miquel on Fri Jun 02, 2017 9:57 am, edited 1 time in total.
HELP. Spanish TVs are brain washing people to be hostile to me.

themrcul
Very interested
Posts: 116
Joined: Fri Apr 15, 2016 2:21 pm

Re: A question about calculating visibilty

Post by themrcul » Thu Jun 01, 2017 1:47 am

Hi all,

Thanks for all of your helpful advice.

I'm really enjoying writing this system, as frustrating as problems can be at times!

Last night after work I think it's finally at 90% working stage! There was a problem where a moving sprite didn't come on screen until a bit too late, so it popped in suddenly - otherwise static sprites, moving sprites and camera targeted sprites are all moving around correctly in relation to the camera and world.

So far, I have decided on a horizontal based scanning approach, where all sprites for each map are exported in their spawn points sorted horizontally (vertical doesn't matter).

Below is an explanation of the system I have come up with. It is long, so please don't bother if it's boring to you!

The engine has several run-time lists used to order data so that run-time checks are minimised (using more RAM but hopefully will be faster).
The lists are:
1) A master list of all allocated sprites in map.
2) An array of Vectors of currently visible sprites. This is to achieve layers of sprites, so that all UI elements can be put in the UI sprites list, and all characters in a characters list, such that all UI elements will always render on top of the characters. There are 4 layers.
3) A Vector of all sprites that have a state machine to handle player control, AI etc.
4) A Vector of all sprites (static and/or statemachine ones) that animate.
5) A Vector of all visible sprites that contain collision. Considering whether to have all sprites that contain collision here, in case off-screen collisions occur, but not sure yet).

At runtime, on map change, all sprites are instanced from the map list in ROM. If they are movable, they are also put into the state-machine list, and allocated a state machine.
If they animated, they are also put into the animated sprite list.

The basic game loop is:
1) Update Sprites
2) Update Camera x and y based on current target location. take note of whether camera moved left, right, up and/or down.
3) Update scrolling map/tiles (based on camera location)
4) VDP_waitVSync();

Just a note on when a sprite is made visible, it:
1) Allocates tile-space in VRAM for all of the sub-sprites necessary to display sprite
2) Allocates hardware sprite indexes and fills out struct with the correct data for that sprite
3) Inserts into visible sprites vector (list) in correct x order relative to other currently visible sprites.
To be made not-visible, the sprite is:
1) Taken out of visible sprites list
2) Hardware sprites freed
3) VRAM locations for tiles freed

In sprite update:
1) Go through all AI and player controlled sprites, and do their state machine update, and determine if they should be made visible/not visible (as per lists above)
2) Static sprite update - based on what I was asking above: given the last frame's camera move, determine if any static sprites should be made visible or not visible and perform that task. There are few checks here because the list is sorted horizontally by x, and the checks to make visible stop when we come across our first sprite out of x range, checks to make not-visible stop when we come across our first visible sprite, and we keep a note of which indexes our first and last visible sprites are in.
3) Update all animated sprites' animations, and schedule VRAM updates for sprites that have reached a new frame. I am considering a
4) Re-link all on-screen sprites.


I am not sure if that "is a lot of work" per frame, or how I would go about profiling such a setup.

But with 12 sprites (1 player character (5 sub-sprites, 45 tiles), 1 AI character (5 sub-sprites, 45 tiles) and 10 static sprites (1 sub-sprite, 4 tiles each) dotted around the map), it appears to be working fine. Obviously this is just a synthetic test, and also only on an emulator, but at least it works!

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: A question about calculating visibilty

Post by Stef » Thu Jun 01, 2017 3:36 pm

It looks like you have redone a lot of stuff the sprite engine can do for you but that way you probably have a custom engine more adapted to your needs and also probably more efficient :)

themrcul
Very interested
Posts: 116
Joined: Fri Apr 15, 2016 2:21 pm

Re: A question about calculating visibilty

Post by themrcul » Fri Jun 02, 2017 2:51 am

Hi Stef,
Thanks for your kind words.
Even if it is just as performant as the built in one it was a very useful exercise for me to write my own engine, and gives me more knowledge of how the system works.
Hopefully it will be more efficient for the exact games I am hoping to make too. :)

Post Reply