Archives for: April 2007, 30


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

Permalink 02:58:43 am, Categories: Artificial Intelligence Module  

Project Description

In this project I expect to cover much of what a Game Engine´s AI module needs. This is:


By movement I am referring to all basic steering behaviours that can be achieved by an entity. This includes seeking, fleeing, wandering, formations, flocking, collision avoidance...


This module will include a graph implementation which will include a static and a dynamic graph creation tool. I will use A*, probably with some minor modifications, to accomplish pathfinding.
It is also probable that, if theres time, I include an IDA* implementation which could be use by games with more complex graphs (but I do not think this is a priority in the project).


Crystal Space is very strong in this area because of its quest property class which works as a great state machine. I have a GOAP (Goal Oriented Behaviour with planification) implementation in mind, but I am not sure of what it would be. I am working on that and I will add some info on this as soon as possible :)

There is much more to do, but I am leaving that for further projects as it is not within the scope of a three month project. Further work within this project should include:




Further description of each module will be added under each category:
- Steering Behaviours
- Pathfinding
- Decision Making

Please, feel free to add any comment or idea to this blog. I will get back to you as soon as possible

Permalink 02:40:49 am, Categories: Steering Behaviours  

In order to achieve better movements and steering behaviours from the entities I plan to make a Steering Property Class "pcsteer".
pcsteer will count of a set of properties and a set of functions, these two will blend to achieve more complex behaviours.

Some of the functions defined in pcsteer are:

Seek a target.

Flee from a target.

Pursue a moving target. This is different from seeking because it calculates the targets position in time T and, then, seeks it.

Wander This is done by randomly changing the entities direction between a given range.

Path FollowingThis will follow a sequence of Nodes. It can be used together with a pathfinding algorythm, ie: A*, to reach more complex targets.

Some of the properties are:
SeparationGiven a set of entities and a radius, a force would be created in order to flee from the center of mass of all the entities that are within the radius.

CohesionThis one works just like Separation but it will seek the center of mass of all the creatures that are outside the given radius.

Collision AvoidanceRight now pcmover checks if theres something between the entities and its target. If there is, it stops moving. Collision Avoidance will work like that, but instead of stoping it will add an evasive force to the entities movement.

How would a developer used all of the above?
Lets say we are this LOTR rip-off where three Trolls are trying to catch a Hobbit in the woods. There would be a bunch of trees we would like not to crash with, but besides from that there would not be any difficult spot to seek so we won´t need pathfinding.

Lets say we already created the entity and added pcsteer to it. We would need to define our steering properties:

* We define a weight for each force in our movement and a distance
* from which we will start avoiding obstacles
float weight = 2.0;
float distance = 7.0;
pcsteer[who]->collisionAvoidance(weight, distance);

* We define a radius for cohesion and separation so our trolls will
* work together without bouncing to each other
weight = 1.0;
float radius = 10.0;
pcsteer[who]->cohesion(weight, trolls, radius);

weight = 1.5;
radius = 5.0;
pcsteer[who]->separation(weight, trolls, radius);

//This have to be done for each troll in trolls

Now, we defined our static properties (they are not so static, we can change them whenever we want, but they will remain the same after any function call.
Now we would probably want to define a basic behaviour, lets say we want the Troll to wander through the woods until he sees the Hobbit:

trollBehaviour(int who){
//its more important not to crash than catching the hobbit
float weight = 1.0;
float radius = 5.0;
float offset = 3.0;
pcsteer[who]->pursue(weight, hobit);
} else {
pcsteer[who]->wander(weight, radius, offset);

As you can see we don´t have to worried for collisions, separation or cohesion while defining our behaviour because thats already defined during the creation of the npc. The idea is to have more complex behaviours too like formations, flocking and swarming, but I will add that later.

The only thing left for me to explain is the radius and the offset in wanders call. This is because the wander function I have in mind uses an invisible circle in front of the npc to calculate its new direction. offset is the distance between the entity and the circles center.

Permalink 02:00:24 am, Categories: Artificial Intelligence Module  

About myself and other stuff no one cares about =P

Hi there!

my name is Mauricio Hollando, I am from Caracas Venezuela and I will be working in an Artificial Intelligence Module for Crystal Space (CEL, actually) during this summer.

I am 21 years old, I am currently studying Computer Science at Universidad Simón Bolívar in Caracas, Venezuela. As you can see, my primary language is Spanish, so I would like to apologize in advance for any mistake you may find in my grammar =).

I don´t have much experience with CS or CEL (so please understand and correct any mistakes I may have) but I do have some experience with games AI.

My intention is to have a complete work plan posted in this blog. I don´t have a complete design yet, but I will before I start working. So, please, send me some feedback before I start messing things up =).

April 2007
Mon Tue Wed Thu Fri Sat Sun
 << < Current> >>
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




XML Feeds

What is this?

powered by