Pathfinding and storing data
Posted 05 January 2007 - 08:58 PM
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.
Posted 06 January 2007 - 12:17 AM
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 (http://www.gamasutra...pathfinding.htm) and Amit Patel's website (http://www-cs-studen...p/gameprog.html)
Posted 06 January 2007 - 11:21 AM
Posted 06 January 2007 - 02:52 PM
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 :)
Posted 06 January 2007 - 03:19 PM
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.
Posted 07 January 2007 - 01:36 AM
- to save memory you likely need to re-calculate information.
- to improve performance, you likely need to store and cache extra information.
Posted 08 January 2007 - 01:37 PM
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.
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users