A* Path-finding

<- Return to Programming blog
As you may or may not know, I am currently working on a game called Mendel's Farm with the rest of the team at Static Games. Over the last couple of days I have been thinking about various ways of adding AI-controlled actors to the game and how best to make them navigate the farm...

I decided that path-finding over a grid will be required to achieve this, so I decided to investigate the A* path-finding algorithm. Before implementing it in-game (in UnrealScript) I decided to create a test implementation in JavaScript using HTML for rendering and the UI. I've uploaded the result here, so click here to run the A* test!

This implementation differs from a base A* implementation in that each cell is given a weight based on the surrounding walls. I added this feature mainly so that actors will not cling tightly to walls and will not turn corners at very sharp angles. The upshot of this is that characters now favour travelling across open spaces rather than navigating tight passageways. This weighting could be reversed to create a stealthy actor that, in contrast, always favours narrow passageways and avoids open spaces.

Keep an eye open on the Static Games site for updates on Mendel's Farm and our other projects! And when you see a fox sneaking towards a chicken coop in Mendel's Farm, you'll know a little bit about the code behind its behaviour...