I've been working lately mostly in fixing bugs.
Pcsteer, PcPathfinder and Celgraph are finished but they do have some bugs yet to be fixed. Some of these are:
- celgraph crashes if you call A* with the same node as initial and goal.
- Pursue in pcsteer calculates wrong velocity some times. I have not find a pattern which describes when this happens.
- FollowTwoWayPath and FollowCyclicPath in celgraph are not working correctly.
- This not actually a bug, but there still some upgrades to be made to A* to achieve better time performance.
I expect to finished doccummenting my code and fixing bugs by the end of the week. I have also been studying for a final test tomorrow, then Ill be completely free.
I have already started looking for a good method to load graphs in an application. By the moment the only way you can do this
is coding a LoadGraph Function inside your behaviours file. I will start working on monday on a loading method through the cel.addons utility.
Finally I'll be working in adding formations to pcsteer and, thats all for now =)
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 =)
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 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;
Cohesion, Separation and Direction Matching (this name is going to change probably for Velocity Matching) options are available now
by pressing keys '3', '4', and '5' in the steer application.
Cohesion will work pushing the entity towards the center of mass of a group of entities.
Separation will push the entity away
and Direction Matching will push it towards the same direction a group of entities have.
I've made some advances in pcsteer. Collision Avoidance is still not working, I've tried many things to solve it but I am having problems with csSectorHitBeamResult, I am using it to detect the nearest collision but, most of the time it fails to detect collisions even if it is in front of a wall =S. well, if any of you know how to fix this, please tell me =P.
However, I added the Pursue behaviour, it can be used in the steering application by pressing the 'p' key.
The npc will then pursue the player.
Pursue is different from Seek in:
1. It continues updating the players position until Interrupt() or StopMovement() are called.
2. It predicts a target future position: target_position += velocity*prediction
So Pursue can be used whenever you want an npc to follow a moving target and seek could be used if you want the npc to look for an object or any other non-moving targets.
Well, thats all for now =-)
I've been working in Steering Behaviours this last weeks and I will continue working on it for about two more weeeks I think.
The steering property class is located at plugins/propclass/steer/
right now it supports seeking (with and withour arrival checking) and fleeing.
I already started collision avoidance but it is not fullu working (I hope I'll find out why tomorrow =P)
I've also created a Steering application which is located at apps/tutorial/steering/
All of the above is located it: https://cel.svn.sourceforge.net/svnroot/cel/cel/branches/soc2007/ai
To excecute the steering application you only need to run: ./steering (./steering -relight the first time).
The steering application is based in walktut, it is actually an upgrade on walktut. It has the same entities plus one npc which is able to perform
any action included in pcsteer.
Here is a little tutorial on how to test it:
1 Activates arrival checking
2 Activates collision avoidance (this is not working right now)
s Seek (The npc will run in the players direction)
f Flee (The npc will run in the oposite direction to the player)
This is all for now, hope some of you have time to download and test this application, the idea is that I could get feedback in time to perform any changed =)
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 =)
This few days I´ve been working in Steering Behaviours.
I´ve been writing some code, basically getting some ideas from pcmover property class and upgrading it.
This property class is based, mostly, in Linear Algebra and High School physics. Most of what I am doing in here is performing calculations with vectors.
For better understanding I will put some images I drew in paint (yeah I know is lame but is the best I could come up with =$)
As you can see, everything is about determining an entities direction to perform its current task.
This task could be seeking, pursuing of fleeing from a target; while avoiding obstacles, or separating
from other entities, etc.
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:
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.
zero or more add-ons.
zero or more mesh factories.
zero or more sectors.
one ore more graphs
zero or more collections.
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:
position x="0", y="0", z="0"/
node id ="1"
position x="50", y="0", z="50"/
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 :)...
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:
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 ;)