How to use some advanced data structures in C

Linked Lists
From Wikimedia Commons

In my eBook, I used only structs and arrays. In fact the commonest “structure” was an array of structs. That was used for bullets, asteroids and aliens ships.The benefits of that are it’s easy to process; I started out by using it as an array and eventually switched to using a pointer to each struct “walking” the pointer through the array, jumping it if you like from struct to struct. Very simple and ideal for a game like asteroids.

You don’t need complexity because that slows things down and the only constraint in the design was making sure I could run everything at 60 frames per second..

C doesn’t come with anything more complex, yet computer science has determined many many advanced data structures that have their uses.

If you were programming a dungeon exploration game, an array might not be the best way to store the dungeon. You’d have multiple levels where each level consist mainly of rooms and corridors. How might you store that? Also there’d be monsters, treasures, traps, transporters and so on in the dungeon.  How would you traverse this structure, guaranteeing there’s a path so that every room can be reached?

Coirridor
Image by Rudy and Peter Skitterians from Pixabay

You might use an array to hold each level but how would you connect levels? Thinking about it I probably wouldn’t. I’d have staircases connecting corridors, traps that let you fall through to a room or corridor below, a transporter that lets you appear in a room or corridor above.

C is flexible enough to support a structure like this but you would have to code all the storage yourself. One way round it is to find an open source library like SGLIB. One reason I chose this is because it lets you create container data structures.

Sglib is fairly low level. It includes code for sorting arrays, for manipulating singe, double and sorted linked lists, red-black trees and hashed containers. As they say “A hashed container is a table of fixed size containing another (we say base) container in each cell. Once an object is going to be inserted into the hashed container, the hash function is used to determine the cell where it belongs and then the object is inserted into the base container stored in this cell. The base container is usually a list, however it can be a sorted list, double linked list or a red-black tree as well. Sglib’s hashed container is parameterised by the name of the base container.”

There are examples provided in the documentation as how to use each type of data structure.

 

Leave a Reply

Your email address will not be published. Required fields are marked *