English Amiga Board

Go Back   English Amiga Board > Coders > Coders. General

Thread Tools
Old 23 February 2019, 12:25   #1

phx's Avatar
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,566
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.
phx is offline  
Old 23 February 2019, 13:26   #2
son of 68k
meynaf's Avatar
Join Date: Nov 2007
Location: Lyon / France
Age: 47
Posts: 3,664
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...
meynaf is offline  
Old 23 February 2019, 13:45   #3
Join Date: Jul 2008
Location: Sweden
Posts: 2,265
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.
Leffmann is offline  
Old 23 February 2019, 14:24   #4

phx's Avatar
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,566
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.
phx is offline  
Old 23 February 2019, 15:08   #5
Registered User

Join Date: Feb 2018
Location: London / UK
Posts: 73
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.
dodke is offline  
Old 23 February 2019, 15:17   #6

phx's Avatar
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,566
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.
phx is offline  
Old 14 March 2019, 01:14   #7

Photon's Avatar
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,818
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.)
Photon is offline  

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 09:10
Calculating speed of an object in a game mcgeezer Coders. Asm / Hardware 6 22 February 2018 18:32
hidden object game for the Amiga Sandro request.Old Rare Games 4 02 December 2014 21:30
Vertical scrolling motorcycle game.. Anyone? Thrash75 Looking for a game name ? 11 18 May 2005 20:44
Bonus! Was sorting out all my game boxes... Chris Nostalgia & memories 29 23 January 2003 19:37

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT +2. The time now is 21:17.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, vBulletin Solutions Inc.
Page generated in 0.06859 seconds with 13 queries