Concurrent AI

[GoogleCodeExporter]

Basically i want some feedback on the idea of this.

Basically when ever i try and create an even slightly complex algorithm for Ai 
such as some fuzzy logic, or a path traversal algrotihm server cycles are 
destroyed.  This completely limits the options that we have with the AI.  How 
possible is it for NPC's to have their AI processed and controlled from a 
separate thread.  Testing AI is fine as i test visual rules on the client, its 
just when server message processing gets blocked it becomes a problem

I'd like some feedback on this, mainly from Spodi.

I think this is going to be important for the progress of AI in Netgore i've 
got some good ideas particularly in a Sidescrolling traversal system.  Got a 
few screen shots of automatic node networks graphically in the client, i just 
want the cpu cycles to implement it :D

Original issue reported on code.google.com by aphro.cag on 3 Apr 2011 at 8:00

[GoogleCodeExporter]

Sounds like what you are thinking of is (in a very basic sense) having AI run 
on one thread, and the game updating on the other. That could be very 
dangerous. You could end up having the AI updating using a state mid-way 
between frames, which is normally fine, but causes trouble when large changes 
are made (e.g. an entity of interest teleports or dies). Exceptions can become 
quite common as well due to referencing objects that are in unstable states.

This can be made safe by using snapshots of the world. But then you have the 
overhead of generating snapshots (and the associated garbage generation), and 
the generated results will have to be applicable for at least the next few 
frames (e.g. a heuristic path-finding that supports being updated on-the-fly as 
obstacles move).

The mapping system, by nature, is quite easy to parallelize. It runs 
sequentially right now, but I have always designed it to run in parallel. So 
the server can, in theory, update using as many threads as there are maps. 
Since the number of maps is generally very high (easily 1k+ for a full game), 
and the map updating imposes the greatest frame update cost, this should be 
sufficient as long as the burden of work is not mostly on just a few maps.

So in short, the ideal (and preferred) approach would one that doesn't involve 
threading at all for the AI. If threading is a must because the computations of 
the AI are really that expensive, things are going to get dirty very fast due 
to all the thread synchronization that will need to be added.

Is the problem mostly due to multiple NPCs trying to perform an expensive AI 
update in the same frame? If so, instead of trying to run things concurrently, 
maybe an interleaved approach would be better. Let some NPCs run the AI during 
one frame, others in the next, and so on.

Original comment by Spodiii on 5 Apr 2011 at 11:48

[GoogleCodeExporter]

Im going to try an interleaved approach, because:

imagine 30 NPC's on one large map, each performing a partial pathfinding 
algorithm, then navigating, all at the same time in one loop... I could improve 
some algorithms but it would be a lot quicker with an interleaved approach at 
least as an experimental idea.

Original comment by aphro.cag on 10 May 2011 at 7:37

• Changed state: Started
• Added labels: Due-Never, Experimental
• Removed labels: Due-Soon

[GoogleCodeExporter]

Original comment by aphro.cag on 29 May 2012 at 10:39

• Added labels: Priority-Low
• Removed labels: Priority-High

[GoogleCodeExporter]

For pathfinding I recoment you have a "pathnodes" pre-calculated before.
A file loaded in server witch tell all available "rootnodes".

for example, if NPC wants to move for CurrentX/CurrentY to DestinationX/Y this 
root its already calculated. NPC should just chose between available root 
options in runtime not calculate them.

I will try to post in forum a calculated pathnodes file for the current 
demogame.

Original comment by [email protected] on 1 Mar 2014 at 2:02