Click here to Skip to main content
11,428,825 members (59,481 online)
Click here to Skip to main content

Path Finder AI

, 14 Jun 2004 CPOL
Rate this:
Please Sign up or sign in to vote.
A class to define a 2D space, put walls, set a start & end point, and return the best path.

Sample screenshot

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.

Sample screenshot

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.

Sample screenshot

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.)

Sample screenshot

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.

Sample screenshot

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:

Sample screenshot

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.

Sample screenshot

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

andrea contoli
Software Developer
Italy Italy
No Biography provided

Comments and Discussions

 
QuestionWhat heuristic function is implemented here within the A* algorithm?? Pin
Member 964004518-Jul-13 11:28
memberMember 964004518-Jul-13 11:28 
Questionmore info about AI Pin
Member 964004516-May-13 5:48
memberMember 964004516-May-13 5:48 
GeneralMy vote of 5 Pin
manoj kumar choubey22-Feb-12 0:48
membermanoj kumar choubey22-Feb-12 0:48 
GeneralRTS Pin
nkka27-May-08 18:26
membernkka27-May-08 18:26 
General[Message Deleted] Pin
Danny Rodriguez27-Jan-08 10:11
memberDanny Rodriguez27-Jan-08 10:11 
Generalmy page Pin
acontoli20-Sep-07 3:13
memberacontoli20-Sep-07 3:13 
GeneralThanks Pin
bumper2-Oct-04 12:23
memberbumper2-Oct-04 12:23 
GeneralRe: Thanks Pin
acontoli4-Oct-04 0:31
memberacontoli4-Oct-04 0:31 
GeneralRe: Thanks Pin
bumper4-Oct-04 4:49
memberbumper4-Oct-04 4:49 
Generalgood Pin
cntdnk6-Jul-04 2:03
membercntdnk6-Jul-04 2:03 
GeneralArticle improved Pin
acontoli30-Jun-04 3:21
memberacontoli30-Jun-04 3:21 
GeneralCool Concept Pin
Labrat00216-Jun-04 21:08
memberLabrat00216-Jun-04 21:08 
GeneralRe: Cool Concept Pin
acontoli17-Jun-04 6:43
memberacontoli17-Jun-04 6:43 
Generalarticle... Pin
(Steven Hicks)n+115-Jun-04 17:10
member(Steven Hicks)n+115-Jun-04 17:10 
GeneralRe: article... Pin
acontoli16-Jun-04 1:06
memberacontoli16-Jun-04 1:06 
GeneralRe: article... Pin
(Steven Hicks)n+116-Jun-04 7:09
member(Steven Hicks)n+116-Jun-04 7:09 
QuestionWhere's the article? Pin
Wackatronic15-Jun-04 12:17
memberWackatronic15-Jun-04 12:17 
AnswerRe: Where's the article? Pin
acontoli15-Jun-04 22:08
memberacontoli15-Jun-04 22:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150428.2 | Last Updated 15 Jun 2004
Article Copyright 2004 by andrea contoli
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid