23 February 2019, 11:25 | #1 |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,496
|
Sorting object positions in an 8-way scrolling game
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. |
23 February 2019, 12:26 | #2 |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
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... |
23 February 2019, 12:45 | #3 |
Join Date: Jul 2008
Location: Sweden
Posts: 2,269
|
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. |
23 February 2019, 13:24 | #4 |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,496
|
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. |
23 February 2019, 14:08 | #5 |
Registered User
Join Date: Feb 2018
Location: London / UK
Posts: 112
|
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.
|
23 February 2019, 14:17 | #6 |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,496
|
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. |
14 March 2019, 00:14 | #7 |
Moderator
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 5,602
|
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.) |
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
8 way scrolling for JRPG game | Marle | Coders. Blitz Basic | 44 | 11 February 2019 08:10 |
Calculating speed of an object in a game | mcgeezer | Coders. Asm / Hardware | 6 | 22 February 2018 17:32 |
hidden object game for the Amiga | Sandro | request.Old Rare Games | 4 | 02 December 2014 20:30 |
Vertical scrolling motorcycle game.. Anyone? | Thrash75 | Looking for a game name ? | 11 | 18 May 2005 19:44 |
Bonus! Was sorting out all my game boxes... | Chris | Nostalgia & memories | 29 | 23 January 2003 18:37 |
|
|