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
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
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.
Please log in or register to post a reply.
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
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.
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 youAI 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 :)
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
Thanks! More input is certenly welcome.
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
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
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.