Demo 3 : It's alive! Basic NPC AI, A* pathfinding

When I wanted to add some basic AI to NPCs, I add no idea how to start. Hopefully, many people before me had already think of it all.

I first started to elaborate the controller class that would become the "brain" of each NPC. I knew I needed some kind of loop and a way to decide what action a NPC is to perform. From there, I built a really basic action called "random move" which really only do what it is named after, move randomly without any purpose. That was a start.

What if I attack this NPC? I want him to follow me and attack if he's range. But how does he get around those buildings? Didn't took long before I concluded I was lacking some basic knowledge on the subject. I then asked Uncle Google.

I found many resource and was lucky enough to find some code in C# to help me understand. Here's some link:

http://www.codeproject.com/cs/algorithms/PathFinderLibrary.asp
http://www.codeproject.com/cs/algorithms/PathFinder.asp
http://www.gamedev.net/reference/articles/article2003.asp

I'm using a very basic A* algorithm that should be good enough for what I want to achieve which is allowing a NPC to follow a target around buildings and other objects. With the tutorials I read, it was easy enough to come to a result. In fact, the hardest part was to remove diagonal movement that for some reason, I've been unable to remove the way it should have been done. Having spent enough time already on this, I simply removed the diagonal coordinates from the coordinates available (instead of raising the cost for diagonal like it should have worked). It shouldn't bring any problem. Anyway, all the pathfinding code is isolated so it's really just a matter of recompiling a DLL if I want to improve it one day.

I'm quite happy with the final result but I feel I'll have to revisit this, performance wise. For now, each "non-static" NPC is running it's AI in it's own thread. When the server starts, each AI is started separately and is independent. In the long run, if I end up with lot of NPCs, I think this might cause some problems.

I don't quite know what is the usual way to deal with this but another way to do this would be to have 1 thread per zone. Each zone is responsible for the NPCs in it and the thread is looping through all NPC. Do NPC 1 action, do NPC 2 action, .... , returns to NPC 1...

Again, the code would have to be optimized to make sure a NPC isn't waiting for another one. The advantage of having each NPC in it's own thread is that it's easy to set cool down time for each action and making sure it is exactly as expected. The commoner in the demo have a cool down time of 1.5 seconds between each moves and attacks. So what's happening is that I let the NPC do whatever action he is currently doing than set the thread to sleep for X seconds, which is the cool down time of the action that have been performed, then function calls back itself to check for next action.

So here's the link to the demo:

Demo 3