Path Finder AI

• Download test window - 13.2 Kb
• Download source code - 44.9 Kb

Introduction

I started thinking the way to build a game AI that allows to define a path from a start point to an end point, through some walls. I created a C# library (path.dll) that allows to define a 2D space (MAXX, MAXY) and to add some "Walls". Walls are nothing else than rectangles. After I add all the walls, the path class computes the AI nodes that allows to turn around the walls. The AI nodes that are "visible" (no wall between them) are linked. So, the class implements a path find algorithm (based on C# delegates used to communicate from AI node instances). The result of this O_O algorithm is a sub class that represents a collection of AI NODE destinations from each AI node. In the sample image, we can see the walls (orange), the AI NODES (red), the start point (blue), and the end point (blue).

I propose a test window to run the path.dll library.

The idea

The idea is to define a 2D space. This is done by initialization of the Cartesio class. This class permits to add walls as rectangles in the 2D space.

After creating the walls, the Cartesio class creates (Create_ai_nodes() method) the AI nodes to "walk around" the walls. In the example, we can see 2 walls (in red) and the associated AI nodes.

Creating AI nodes, Cartesio automatically creates the "visibility arcs" that links nodes with each other. A visibility arc can be seen as a line that links 2 nodes without "touch"ing a wall. (See example.)

Finally, Cartesio creates for each node, a list of destinations, and the adjacent node to walk through to reach the destination (I call it AI_star). So, when we are in a node (or we can see it), we know the next node to go to reach each other node.

Finally, the class Super_path is initialized by passing a Cartesio object, and a starting point P1 and an end point P2. The Next() method "moves" P1 to P2 step by step.

While (!(supe_path.Next())) { //render 2d schene }

Using the code

You can see in the demo code I submitted, how the use of the Cartesio Super_path classes is really easy:

// initialize Cartesio with a 2d space of 300 X 300
  cart = new Cartesio(300,300);
  // add  walls to the 2d space
  cart.AddWall(56,56,100,10);
  cart.AddWall(156,15,11,231);
  cart.AddWall(10,135,114,26);
  // creates ai nodes and ai_stars for each node
  cart.Create_ai_nodes();

It might take some time depending on the number of nodes (with 80-90 nodes, we have acceptable time, remember that this operation has to be done only once). The number of visibility arcs influences creation time too.

 // initialize Super_path with start and end point , and Cartesio object.
  Np = new super_path(P1,P2,cart);
  
   // Next() consent to move the point Np.Pa on the path from P1 to P2
   while (!Np.Next())
   {
    P = Np.Pa;
    // render scene..

Optimization

When you put one wall over anther wall (or another set of walls), then the Create_ai_nodes method discards the non-useful nodes that are positioned into a wall. See example:

Delegates and the find path algorithm

I assume that the reader knows how delegates/events work in C#.

I tried to explain how to find out the best choice from the adjacent nodes for a node S to reach a node E.

First of all, during the creation of AI nodes, we create a delegate for each node, and we add to the "listener" list represented by that delegate, all the adjacent nodes.

To go from S to E, let's start from E (backwards). E "casts" a message that contains a reference to E (To), a reference to S (From), and a reference to the node that casts it (Through) (in this case, E); the message contains also a distance D (0 in this case).

When a node receives a message M:

• if it's the first message, it stores the distance D + dist(this, M.Throu), and it casts a new message changing D with D + dist(this,M.Throu) and M.Throu with itself;
• if it's not the first message, if D + dist(this,M.Throu) < the distance stored in the node, then it stores the distance D + dist(this,M.Throu), and it casts a new message changing D with D + dist(this,M.Throu) and M.Throu with itself;

For each message M received by S, S considers the one with min M.D, and so S knows that it can reach E passing from M.Trou.

In the next figure, we se an example of message propagation form E to S (blue arrows). The example shows only some messages. When S receives messages 9 and 10, it evaluates (considering the distance carried by the messages) which path is the best.

How To Use Test Window

Test window's interface is very simple. You can draw Walls (move mouse on screen while left click). After that, remember to click "Create AI Nodes". Then you can set the start and end points (right and left click) and see the origin point reach the destination. (It's a kind of click and go interface). You can also click on Simulation to see an automation on 2000 paths to strongly test my work. Last but not least, you can clear the walls, so you can redraw them.

Hope you enjoy it and return me some good suggestions.