Commander X16

After about 9 months of hibernation, I have started coding on my GhostCrusher game again.

Quite a lot of time has been spent leaning about path-finding algorithms and I started implementing the A* algorithm. I ended up with a very simplified version that can probably not even be called A* as the ghosts only look one field ahead. My thinking is that even though the ghosts are "stupid", there is a reasonable chance that they will find their way to the player.

So far I only have 2 levels and I have added an animation of a play through. When the player is hit by a ghost, he dies and at the moment that means that the game resets the system.

You can follow my slow progress on https://github.com/JimmyDansbo/GhostCrusher/

Proper pathfinding was not common in games of the time because of how expensive they are to execute. Even games as late as StarCraft didn't implement "proper" pathfinding such as A*, instead choosing various strategies to "wrap around" obstacles and get out of problem areas. Actually, since players' expectations for map size has increased almost as much as the CPU power required just to manage and draw those maps, pathfinding has remained a difficult problem, with novel solutions still being invented, which all have pros and cons under varying circumstances.

So don't worry if you never get A* running at speed on an X16. :3

I made an "AI" for the ghosts in Chase Vault based on the original PacMan algorithm. It's not a true pathfinding algorithm, but a really stripped down procedure that is based on goal locations. To make it work, the mazes need to be constructed in a way to allow for it, with no dead ends.

4 hours ago, SlithyMatt said:

To make it work, the mazes need to be constructed in a way to allow for it, with no dead ends.

That is one of my problems. Since the player is able to move walls around, I can not ensure that a ghost will always have a path to the player. At the moment I am fairly happy with how the ghosts move and with more ghosts moving at greater speeds, I am certain this game can become a challenge to play. At the moment I have the ghosts moving very slowly as I am not very good at playing the game and it gives me better time to figure out how to deal with the ghosts.

I've found on other projects (including one I did with 8-bit assembly back when it wasn't an absurd hobby) that Dijkstra's algorithm scales down well to very limited systems. Basically, just turn every open tile space in your maze into a node and build a graph from that. Your graph building can stop once you extend it to whatever area you want to move your automaton towards. That way, you can just rebuild the graph every time the maze changes.

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

11 minutes ago, SlithyMatt said:

That way, you can just rebuild the graph every time the maze changes.

Yeah, I believe it is actually Dijkstra that i have ended up with, just very simplified.

Every time a ghost needs to move, it calculates the distance to the player for all open fields that it can move to in a single step and then just chooses the field with the shortest distance. If necessary, I might end up adding some sort of randomization like David has done for the Planet X3 pathfinding.

Btw, just want to add that Computerphile has some nice videos on Dijkstra's- and A* algorithms

https://youtu.be/GazC3A4OQTE

https://www.youtube.com/watch?v=ySN5Wnu88nE