Despite lack of activity here I have been very busy programming cool stuff which I hope to get around documenting and sharing with you all.
I need to implement the A* algorythm for one of my projects. Its a fairly common to speed up of the implemention to use a binary heap for the open list because of its O(log(n)) insertion and O(1) removal properties. As I code it up I thought it would be nice to share my binary heap implementation, something which can be a bit fiddly to get right in practice. I wrote a little fuzz tester to nuke it, so that I can be fairly sure it works correctly.
I chose to make the size fixed at compile time for simplicity, and becaues I am happy to terminate a pathfinding search that exceeds a fixed open list size, as old school games used to do. It should however not require much work at all to grow the heap size when a node is pushed when currently at full capacity.
I will also leave you with this picture from my latest project:
I love the Bitmap Brothers, and especially the Chaos Engine (Z is also up there). I have so many fond childhood memories of being at my friends house in front of his Amiga500 getting our asses kicked with that game.
A while ago, I really dedicated myself to remaking The Chaos Engine as best I could. This would be a lesson in sticking with a project, a little longer then just proving a core concept. It would teach me about making the tools used in creation of a computer game. I learned how to program more complex enemy AI then I was used to. An entire engine was also designed and programmed just for this project. i implemented a simple custom scripting language for the game. All blitting operations and audio mixing was also done by hand too. In essence, this was by a long shot the most ambitious project I had ever taken on. Everything is programmed using fixed point math also, there is not a single float used anywhere in the source code. All of the path finding is done using the A* algorithm. Also all the collision checks are optimized by maintaining a quad tree for the entire level.
Below is a video of the project as it was when I finally moved on to work on something else. I don’t feel at all disappointed at having abandoned this project because so much was learned in the process.
One item of note was the players companion AI. That was a very fun challenge to program since it was critical that he should be actually helpful in the game.
At a basic level this character operates by means of a strange state machine and blackboard hybrid. The player can be in only one state at a time. A state can return naturally to another state if it specifies to do so. A state can also at any time be interrupted by a transition to a state of a greater priority.
Each priority level of this AI has an expert associated with it, thus each frame, each expert is contacted to see if it has a plan for the AI. Then the plan of the highest priority is selected as the active pursuit. For this AI there was 6 priorities listed below, highest first.
AVOID (avoid enemies and bullets)
ENGAGE (find a good attacking position if not in one)
SHOOT (fire at the most convenient enemy we can find)
CATCHUP (do not stray too far from the player else follow any path we have)
RETHINK (find a new path to our destination)
PICKUP (collect any coins and bonuses around us)
As you can see from the video, even in this early stage of implementation it already looks quite intelligent at times. The AI sidekick was the last thing I added to the project, but one of my favorite things I have programmed.
I may re-examine some elements of this project later and explore them in more depth since there were many very common programming problems that I found nice solutions too that I would like to share. Also I think I will release all the source code too at some point in the future, as it may be of use to someone else.
Bit-Hacks Pixel Dungeon 