Sorting object positions in an 8-way scrolling game

[phx]

In a 2-way, i.e. plain horizontal or plain vertical, scroller you can avoid a lot of unnecessary comparisons when you keep your objects sorted.

For example, in a horizontally scrolling game, you put them into a doubly linked list and have a pointer to the leftmost and rightmost object currently visible on the screen. These pointers can be easily updated when moving the visible region. Ok, inserting and deleting objects requires some extra checks with these pointers, but it is much better than checking the position of all objects in the game. I especially liked to use this method on a list of tile animations (in Sqrxz, Trap Runner).

But when it comes to 8-way scrolling games I still have to find a better way than checking the position of all objects. Having them sorted in a vertically and horizontally linked list at the same time doesn't really help.

Linking them to a map position would be theoretically possible, as the scroll-engine knows at any time which tiles enter and leave the visible display. But this additional information would make the map much too big. In Sqrxz I used 8-bit maps, which just represented a 0-255 tile code, while in Trap Runner I am using 16 bits with some extra information (solid, tile-type, etc.). More than 16 bits would restrict me to very small maps.

Has anybody ever developed a good algorithm to minimize the required checks for currently visible objects on screen?

In my last public 8-way scroller, Solid Gold, this was a real problem. When you do not kill all the monsters after activating them, the comparisons become more and more, and in the end the game cannot keep the 50Hz.

[meynaf]

If facing that problem i'd first try to build some kind of a cell cache. Then extra information isn't for full map but only for the current area.
Just an idea...

[Leffmann]

A simple way is to divide your game map into f.ex. 128x128 pixel regions and bin your objects into the correct region as they move. You can then directly map your view rectangle to the relevant regions, and finally do an exact comparison of the objects inside with your view.

You could almost think of it as a hash table where each region is a bucket, which you index using the X and Y position after discarding the 7 least significant bits.

[phx]

That's actually a quite good idea! Thanks both of you!

It could even be easier/faster to discard the least 8 bits of an coordinate. So I just use the high-byte to determine the hash bucket. On the other hand it could mean some more objects to check. I have to experiment a bit, I guess.

[dodke]

I was thinking to have 2 lists of pointers to game objects, active and inactive. If you for example decided that anything more than a whole screen or 2 away can be inactive you don't need to check them very often. A small fraction like 1/16th of the whole list is probably enough. If you don't have hundreds you might even be able to iterate through it one object per frame so 50 a second.

[phx]

Indeed, I have these lists with active and inactive objects.

Doing the position checks less frequent for objects which are far away is certainly another good idea! Thanks.

[Photon]

Two degrees of freedom is indeed what makes it hard.

Linked lists are it, to get more you have to bin them into lower resolution (Heap sort, or without comparison, some sort of magnitude/binary sort but this will leave big gaps for small number of objects or else binning friends in with strangers.)