Progress Report #9: AI Mutterings

So I've started work on Monster AI. This is going to be quite a big task. And already it has me wishing for some of the functionality of C#. The reason? LINQ.

Every turn, the AI subroutine will process the list of currently active monsters on the level, determining what to do from their programmed behaviour, current condition, hatred for the player and so on. So I need to find what monsters are currently active. Initially I have to scan the entire level looking for monsters who are both alive and awake (i.e. aware of the player's presence, usually by being in line of sight or line of sound of him/her).

I started off with storing a list of monster pointers in an integer array. Of course, to get any performance out of this method, I need a quick way of determining if the monster is already active. So I just search the array. Whoops. Its an unordered basic array of integers. Searching performance is atrocious.

Being able to search through arrays as if they were a dataset,e.g.


IEnumerable query = from s in names where s.Length == 5 orderby s select s.ToUpper();

would be the answer to this. Instead, lacking such functionality, I've decided to use an additional TObjectList to store the active monsters. Monsters that awake are added to the list, and ones that are killed are removed. Its not ideal, but it does the job, and does it reasonably quick.

Which is needed as implementing pathfinding for monster movement is pretty processor intensive. I've been experimenting with the free Delphi pathfinding components available here (demo exe here) and they seem to do the job, but for every monster that wants to move towards the @ (a later enhancement I'll add is moving them towards the last known position of the @) I need to recalculate the terrain costs of the entire level, and the only way for now to do that is to iterate through the entire level one tile at a time. Delving into the source code of the components reveals that they use a TBits array in their calculations, so I'm not sure there is much more room for optimisation.

Anyway, the AI is still a work in progress - dealing with finding the correct direction to represent monsters fleeing "directly away", (for whatever reason) from the player is proving to be a pain but for now here's a video showing the beginnings of the path-finding in action:

Since no combat has been implemented yet, the monsters cannot be killed, and near the end of the video you'll notice the @ stepping onto a monster, but the basics are there and starting to shape up nicely (that sometimes the screen draw takes more than 1 ms is due to the green diagnostic messages being displayed in the message log - standard performance even with the cost of terrain calculations being performed multiple times is still below a millisecond)