Category: Pathfinding


Permalink 03:43:12 pm, Categories: Pathfinding  

Pathfinder propclass!

Hello there,

I know I have not written for a while, but thats basically because I had nothing new to say =P.

CelGraph is finished and it appears to be working correctly, however there are still some tests to be made.
Now, when I was testing it in a graph application I noticed how hard it was to create a path, call the graph, then call
pcsteer to follow that path and... you get the point.

So i created PcPathfinder, this class has similar functions to pcsteer (in fact it behaves very similar):


Seek will seek a position in the world using the graph, this way entities will be smarter to use certain paths instead of crashing against walls.

Pursue will do the same except that it will continue running A* in case the target has modified its position (as you can see this costs a lot)

Wander will use a function call RandomPath(int distance) in CelGraph which will create a random path of deepness distance ie: a random path with distance nodes.

Follow Cyclic Path will follow the indicated path and it will start over again once it reaches the end.

Follow One way Path will follow the indicated path and it will stop at the end.

Follow Two Way Path will follow the indicated path and it will follow it backwards once it reaches the end.

I thought these three functions may be useful for developers in case they want to set certain paths for there entities (guards for example may use this).

Finally I am thinging of adding a multiplier (float) property to edges.


Well, for the moment the cost between two edges is always the euclidean distance between them. But this will cause serious problems in games where you move slower in the mud or grass, etc. So, I will add this property, it will be 1.0 by default and it could be changed by the user with a SetMultiplier function.

Well, this is all for now, pcPathFinder still have bugs so Ill be working in this during the next week or so =)


Permalink 12:35:03 am, Categories: Pathfinding  

celGraph almost ready


I will paste here the interfacte of CelGraph and its components. At the moment I am finishing some details on A* and I will soon be finishing an application for testing CelGraph and pathfinding.


struct iCelNode;

struct iCelEdge : public virtual iBase
SCF_INTERFACE (iCelEdge, 0, 0, 1);

virtual void SetState(bool open) = 0;

virtual void SetSuccessor(iCelNode* node) = 0;

virtual bool GetState() = 0;

virtual iCelNode* GetSuccessor() = 0;

struct iCelNode : public virtual iBase
SCF_INTERFACE (iCelNode, 0, 0, 1);

virtual void AddSuccessor(iCelNode* node, bool state) = 0;

virtual void SetMapNode(iMapNode* node);

virtual void Heuristic(int cost, iCelNode* goal)= 0;

virtual csVector3 GetPosition() = 0;

virtual csArray iCelNode* GetSuccessors() = 0;

virtual csArray iCelNode* GetAllSuccessors() = 0;

virtual int GetHeuristic () = 0;

virtual int GetCost () = 0;


struct iCelPath : public virtual iBase
SCF_INTERFACE (iCelPath, 0, 0, 1);

virtual void AddNode(iMapNode* node) = 0;

virtual void InsertNode(size_t pos, iMapNode* node) = 0;

virtual iMapNode* Next() = 0;

virtual iMapNode* Previous() = 0;

virtual bool HasNext();

virtual bool HasPrevious();


struct iCelGraph : public virtual iBase
SCF_INTERFACE (iCelGraph, 0, 0, 1);

virtual void AddNode(iCelNode* node) = 0;

virtual void AddEdge(iCelNode* from, iCelNode* to, bool state) = 0;

virtual iCelNode* GetClosest(csVector3 position) = 0;

virtual iCelPath* ShortestPath(iCelNode* from, iCelNode* goal) = 0;


Soc Starts!

Hi there!

Well, coding time started this monday and I wanted to keep you informed on my progress and my schedule for the next weeks.

As I explained before, I will be working in three main sections (Steering Behaviours, Path Finding and Decision Making). I am planning to work four weeks in each of them (hoping I only need 3 weeks for the first too). I will be starting in steering behaviours (which is needed by pathfinding), then I'll be covering Pathfinding and, finally I'll be working with Decision Making.

After all of this I will make a simple but complete application showing how to use all of what I made.

I hope I'll be soon showing you some code from steer property class, I've already starting coding and I am waiting to test it in some application.

That's all for now,
talk to you soon =)


Permalink 04:33:59 pm, Categories: Pathfinding  

Statically definition of graphs


I have been reading section 4.16 of Crystal Space manual (Format of Map Files). I have already think of a way to define graphs in an xml, first of all I think the new world file should look like this:

initialization part:
one texture specification section.
one material specification section.
one shader section.
one sounds section.
one variable section.
one plugin section.
one settings section.
zero or more start locations.
zero or more library specifications.
zero or more keys.
world elements:
zero or more add-ons.
zero or more mesh factories.
world definition:
zero or more sectors.
one ore more graphs
zero or more collections.
action section:
one sequence section.
one trigger section.

I think one graph should be specified for each sector and a special kind of edge should be included in the nodes which connect two or more sectors.

This graph section should look like this:

node id="0"
position x="0", y="0", z="0"/
edge to="1"/
node id ="1"
position x="50", y="0", z="50"/
edge to="0"/
edge to="-1" sector="sector_name"/

BTW: this is meant to be xml but I didnt get to write it correctly, I will re-write this later :)...


Permalink 03:21:05 am, Categories: Pathfinding  

Graph Implementation

Mostly what I have about our graph implementation is that we should use a vector-like structure to store nodes and edges.


Most of the time graphs will be loaded during the begining of the applycation and they will rarely change during the game. This means, we will only add nodes and edges once and almost never erase them. This unless a bridge explodes, an avalanche blocks a way or a door opens(and even in this case we can mark those edges as blocked or unblocked without erasing them).

This means, most of the time, almost every second we will be performing searches over the graph.

Vectors are known for their slow adding/erasing performance but very good searching performance becuase they maintain all their elements within the same memory block (this helps with element indexing).

I am not saying I will use vectors, but something like that. I have to explore what structures CS offers for me to use :). Maybe you can give me some ideas on that.

Besides from that, I think graphs should be aloud to be defined dynamically (by an automatic graph generation algorythm) and statically (defined in world files).

I have some ideas on dynamic graph creation, these are:

Polygonal Meshes
The level is made of polygons connected to other polygons. Each polygon acts as a node in the graph. Nodes are connected if their corresponding polygons share an edge

Dirichlet Domains, also known as Voronoi Diagrams
Graphs can be defined by Dirichlet domains by defining a set of points (called characteristic points) in the level which will serve as nodes. Each node has a region of influence around it, and it is connected to all other nodes within its region of influence.

Points of visibility
I am short on time right now, but I will add a description, later ;)

November 2017
Mon Tue Wed Thu Fri Sat Sun
 << <   > >>
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      




XML Feeds

What is this?

powered by