Linked Lists using Custom Types
Blitz3D Forums/Blitz3D Beginners Area/Linked Lists using Custom Types
| ||
| Here is some minimalist code to create and walk linked lists. There are 3 sections of code: 1 Forward linked lists 2 Backward linked lists 3 Bidirectional linked lists Anthony Jordan ; --------------------------------------------------------- ; Forward Linked List AKJ 30-Jul-03 ; Create a forward-linked list of 4 items, then cycle through all the items. Type item Field id Field nextitem.item ; This field is being recursively defined as custom type 'item' End Type ; Create the list address.item = Null ; Variable to point to items in the list For i=1 To 4 mylist.item=New item mylist\id=i If address<>Null Then address\nextitem=mylist ; Forward link of the previous item address = mylist ; Address of the current item Next ; i ; Fill in the forward link of the last item address\nextitem=First item ; Now walk the links and display the list mylist = First item ; Arbitrary starting point For i=1 To 10 ; Walk the list repeatedly Print " "+mylist\id+" "+Str$(mylist\nextitem) mylist = mylist\nextitem ; Use the link to go to the next item in the list Next ; i WaitKey() ; --------------------------------------------------------- ; Backward Linked List AKJ 30-Jul-03 ; Create a backward-linked list of 4 items, then cycle through all the items. Type item Field id Field previtem.item ; This field is being recursively defined as custom type 'item' End Type ; Create the list address.item = Null ; Variable to point to items in the list For i=1 To 4 mylist.item=New item mylist\id=i mylist\previtem=address ; Address of the previous item address = mylist ; Address of the current item Next ; i ; Fill in the backward link of the first item mylist = First item mylist\previtem=address ; Now walk the links and display the list mylist = First item ; Arbitrary starting point For i=1 To 10 ; Walk the list repeatedly Print " "+mylist\id+" "+Str$(mylist\previtem) mylist = mylist\previtem ; Use the link to go to the previous item in the list Next ; i WaitKey() ; --------------------------------------------------------- ; Bidirectional Linked List AKJ 30-Jul-03 ; Create a bidirectional-linked list of 4 items, then cycle through all the items. Type item Field id Field previtem.item ; This field is being recursively defined as custom type 'item' Field nextitem.item ; Also recursively defined End Type ; Create the list address.item = Null ; Variable to point to items in the list For i=1 To 4 mylist.item=New item mylist\id=i If address<>Null mylist\previtem=address ; Backward link of the current item address\nextitem=mylist ; Forward link of the previous item EndIf address = mylist ; Address of the current item Next ; i ; Fill in the backward link of the first item mylist = First item mylist\previtem=address ; Fill in the forward link of the last item address\nextitem=mylist ; Now walk the links and display the list mylist = First item ; Arbitrary starting point For i=1 To 10 ; Walk the forward links Print " "+mylist\id+" "+Str$(mylist\previtem)+" "+Str$(mylist\nextitem) mylist = mylist\nextitem ; Use the link to go to the next item in the list Next ; i Print "" For i=1 To 10 ; Walk the backward links Print " "+mylist\id mylist = mylist\previtem ; Use the link to go to the previous item in the list Next ; i WaitKey() |
| ||
| I don't get it. Why implement your own linked lists for custom types when they're built-in to Blitz? |
| ||
| The code is intended as a skeletal structure. You can adapt it to link items in non-standard ways. Indeed, the given code implements circular lists which are not built-in to Blitz. Another point is that the code shows how easy it is to determine the addresses of items in a list. A subset of these could then be stored in a separate array (or list) to provide direct access to the start of sub-lists within the main list. Also, the links can easily be altered at runtime, which means (for example) that the list (or any subset of it) could be sorted first by one field and then later on by a different field, simply by appropriately rewriting the contents of the link fields. This could (for example) be a useful way of rearranging the visibility z-order of a large list of objects from various viewpoints. My incentive for producing the code was to make it easier for me to convert some C programs in my possession to BlitzPlus. These programs make heavy use of list-like data structures which did not map easily to Basic code. Anthony Jordan |
| ||
| Thanks for the explanation |
| ||
| I use home-made linked lists like that in my tile engine to store all objects that are on the same tile on the map. As an object moves from one tile to the other, it is removed from the list of the tile it left, and added to the list of the tile it moves to. These lists are then used in collision detection. Suppose the player is on a given tile; in order to check for collisions with enemies you now only have to check the linked lists of enemies in that tile and the adjacent tiles (assuming no object is bigger than one tile), which is much better than checking for collisions with all enemies! These lists can also be used for more efficient z-order drawing, drawing first the top row of tiles and the objects on those tiles, then the next row etc. All in all I can really recommend this way of doing a tile engine. There's of course a little bit of extra work involved in calls to functions for handling the lists, but, with things like collision detection, or for instance AI where the enemy has to look for nearby enemies, the amount of time saved is bigger as you avoid the quadratic aspect of checking everything with everything. |
| ||
| Hmmm, what happens if the player is between 2 - or 4, for that matter - tiles? The last time I did a tile-based game with loads of enemies, I used a 'shifted grid' method for collision detection which also means you don't have to check everything-colliding-against-everything. Worked very well. Anyways... |
| ||
| The player can never be *between* two tiles (well, depending on the program of course). In my case the position of the player is the position of the upper-left corner of its image. Now, this point is always on a tile, and never inbetween two tiles; when you move from one tile, you always end up on another tile. Of course, the image of the player can be in two tiles at the same time (or 4 tiles even) when you are moving near to the border between two tiles. But this is why for collision detection, you have to check the tile you are technically in *and* the adjacent tiles to take overlap into account (the player image could stick out onto an adjacent tile, and likewise, enemies could also be sticking out onto your tile). I don't know how the 'shifted grid' method works. In general I would think that the trick is to somehow have a link from location (tile) to objects on that location. That way, you check for nearby locations, and through these locations you find the nearby objects. That is what I do using the linked lists. Is 'shifted grid' something similar? |
| ||
| Shifted grid (if I can remember :)) basically involves dividing the play area into a grid and then only checking for collisions between the objects that lie within the same grid. That is, only check for collisions against other objects that are near by - this avoids redundant checks such as checking if an object is colliding with another on the other side of the play area. However, it's possible a collision can occur between two objects that lie on the edge of two adjacent grids so the grid has to be 'shifted' up, down, left, right and the collision tests performed again. There are other refinements that can be made to the basic algorythm but that's basically it. It's an especially effective technique when you has loads of objects in a large (scrollable) playing area. |
   |