Pathfinding and storing data

Zcumbag 101 Jan 05, 2007 at 20:58


I need some help here in fully understanding how I should go about this task of mine. I’m a .Net developer that really never done anything gamelike, only other sorts of software development. I’ve started reading up on game engine programming and mostly pathfinding and A*.

Let me describe a situation I want to solve. Simply explained I want a bunch of objects(persons) to move about in a space(a apartment) during a time period (of lets say 12h). The apartment have diffrent rooms with diffrent activities, a room with a pool table, another with a TV etc. The objects(persons) also have a set of properties describing their intrest in watching TV, playing pool etc. This should of course be a factor of where the objects more likely will move to, as would the fact that some objects may avoid eachother or perhaps strike up a conversation.

Still reading? Thanks…

My big issue with this is how to store their positions and moving directions. The easiest way i suppose is to have a grid that makes up the entire orientation map. But I would prefer to store positions and direction (and speed?) But I suppose this is a harder way of going about?

Also, the time issue… should i have each object evaluated/moved, say every (game-)second. Or is there a smarter way of storing (because I DO need to store for recreation purposes) the objects position (and attributes) at every given second?

Any inputs or further refrences would be greatly appreciated.


6 Replies

Please log in or register to post a reply.

Jare 101 Jan 06, 2007 at 00:17

This probably belongs to the AI forum. That said:

A grid is a good topology to reason about for pathfinding. You can store the position (and destination) of an object with any precision you want, but that position will always correspond to a grid node. Once you calculate a path through the grid nodes, you can “smooth” and “beautify” it so it doesn’t move from grid node to grid node, but continuously in the manner you described (position, orientation, velocity).

Most games update their entities’ logic several times per second; 10 or 15 are very common update rates.

Classic resources are Bryan Stout’s article ( and Amit Patel’s website (\~amitp/gameprog.html)

GroundKeeper 101 Jan 06, 2007 at 11:21

If the apartment you are describing is fairly small you could consider to have a more unnatural pathfinding. Perhaps create a graph covering the apartment. When using a more high-level network for paths of the apartment you could simply use PID (google to learn more) to navigate the network together with your A*. You could also (if you have the ambition) try to implement dynamic A* which reads the mesh (apartment + interior) and creates a grid asit goes. Couldn’t find an good resources just now but what I have read is that it is well suited for pathfinding in complex environments.

Good luck!

SpreeTree 101 Jan 06, 2007 at 14:52

What kind of path finding you use depends on the size, complexity and dynamic nature of the environment.

If you have a static, simple space, you should look into way points or pre-omputed paths. Dynamic A* might be more complicated than you need, but only you can decide that.

Here’s a couple of good links for you
AI Path Links - A little way down the page.
Gamasutra Article - You need an account to access this one.

I’m not sure what problems you are having in regards to storing the positions and directions. Surely each person within the environment has it’s position and directions stored internally? Speed is probably not needed, if you want varying speeds, you could just have state flags ‘walking’ or ‘runnning’ for example.

Hope some of that helps :)

Zcumbag 101 Jan 06, 2007 at 15:19

Thanks for all the input.

I can now probably figure out a good path-finding algorithm, my main problem is how to go about storing the information. None of the objects will be interacted with in realtime by the user. The user is rather overlooking the apartment.

The user should be able to watch what’s happening in the apartment at a given time. So I somehow have to store information of where the objects are at all time, so that the user can access it. Since that is rather large amount of data to store, I’m thinking of storing basic values so that the positions and movements can be recreated at request from user.

The question is, however, that I at request from user I have to recreate the positions and movement all the way from the root-node. Wich might be a performance issue if the user requests many diffrent points in time. (Not AI anymore?)

I’m still thinking a lot of how to go about, but I’m definetly moving forward.

Thanks! More input is certenly welcome.

Jare 101 Jan 07, 2007 at 01:36

Unless you have many thousands of objects, storing the object positions and such should be ok. To give you an idea, in Praetorians we were moving up to 5-6 thousand soldiers on a P3-600MHz with 512Mb of RAM, and they all had significant data (position, orientation, path, health & attack, animation, targetting, etc). The path and AI data for each of them will take much more space. Use the simpler approach, get your program working, and then optimize if you see memory or performance bottlenecks, but remember that those optimizations often go against each other:

  • to save memory you likely need to re-calculate information.
  • to improve performance, you likely need to store and cache extra information.
SpreeTree 101 Jan 08, 2007 at 13:37

As mentioned, you only need to re-calculate the positions/orientations if you are working with a limited tool set. Any ‘standard’ computer can easily handle a few thousand floats to represent positions and orientation.

The problem really comes from looping though these many objects - are you going to group them, update them all every N number of frames, use space partitioning to limit what needs to be updated etc.

Of course this all depends on how many entities you actually have.