🔒 Locked

Pathfinding and memory via sql database?

Started by BUnzaga Aug 14, 2006 at 9:32 PM 2 replies 1.6k views

Original Post

Aug 14, 2006 at 9:32 PM

Hey all, Im real new to EVERYTHING involved with 3d game programming, so please bare with me if I say something real ignorant. So I have been messing around with a program called DX Studio which is pritty sweet, and I have come to a point where I want to start doing more advanced things with 3d objects, such as AI and pathfinding, inventory, all that stuff. Perhaps do some SMALL multi player options. (like group missions) I have been reading everything I can find about pathfinding, and the way it works and the EXACT math equation that is used, etc. Although I have read a ton of stuff on the subject, it is still only a vague idea, which I understand, but its still out there, like a dream your just waking up from. Ok to get to my point. I was thinking of creating a system where I list all my 'nodes' via a database with their different weights, and directions, etc listed as rows in a sql database. I then would setup my pathfinding A* code to first check the destination node and the 'home' node against the database and if there isn't a path listed, it would go through the A* script as normal. The catch here is that once it determines the correct path, I would then make it save A)the destination node, b)the home node and c)the path determined, to the monsters 'memory database' Now if it does find that 'destination node' and 'home node' are in the table, it just loads the path that was saved the last time and uses it. A couple ideas I had to optimize this would be maybe just use it for node regions. Instead of scanning every single node, just have a region check, so check the region im in, check the region the target is in, load the path in the database to that node regeion, and then in the background I could be calculationg what the monster should do once it gets to that region... Another idea would be to only have the 6 most frequently visisted paths in my database. This way if the player enters a room, the monster knows exactly where the door is so it doesn't have to think about how to get to it. It goes to the door, then from there it will have to kick into the pathfinding script. You could also code in other things, but the general idea is rather then use graphical representation of the nodes in the 3d engine, why not just use a sql database, or a table or some other non-3d form? Would the time it took to look up this information be a ton slower then just calculating a path?

Rasmadrak

Aug 15, 2006 at 3:00 AM

Is a string longer than another string?

General coding - First you code, then you optimize!

chosendl

Aug 16, 2006 at 5:29 PM

I think that instead of trying to develop regions and routes during playtime, your map editor could calculate and generate all the possible routes and regions at design time. Your units would have to do very litte thinking when choosing a path during playtime, this would save tons of processor performance.
I also dont see why it has to be stored in a database! With the amount of memory available these days, you could load up that particular maps routes into memory and then just work off that until the game is over and a new map is loaded.

Timkin

Aug 16, 2006 at 10:03 PM

One must always decide between the usual tradeoff: time versus storage. If you have lots of time or very little storage, you perform your computations online. If you have ample storage, then you can use offline time to precompute pathing solutions and store them for use during play.

There is already an established method similar to what you have described that saves you a lot of storage space as well. Consider a set of nodes A,B,C,... etc. Not all nodes are connected to each other. The set of nodes and their connections form a graph. For instance...

     A --- B    /       \       C -- D -- E         \  /          F

We can store pathing information for this graph in a matrix. Each node is represented in both a row and a column...

  |A | B | C | D | E | F |-------------------------A |  |   |   |   |   |   |-------------------------B |  |   |   |   |   |   |-------------------------C |  |   |   |   |   |   |-------------------------D |  |   |   |   |   |   |-------------------------E |  |   |   |   |   |   |-------------------------F |  |   |   |   |   |   |-------------------------

Now, reading rows as start nodes and columns as destination nodes, the element stored at (i,j) is the node that you must go to if executing a path from node i to node j. A '0' (or any other appropriate symbol) is used to denote no movement (i.e., completion). So, the matrix looks like (for the above graph)

  | A | B | C | D | E | F |-------------------------A | 0 | B | C | C | B | C |-------------------------B | A | 0 | A | E | E | E |-------------------------C | A | A | 0 | D | D | D |-------------------------D | C | E | C | 0 | E | F |-------------------------E | B | B | D | D | 0 | F |-------------------------F | E | E | D | D | E | 0 |-------------------------

To use the matrix, you look up the starting node and the destination node. The entry tells you which node to move to next. So, for example, a trip from node A to node E says to go to node B. Now node B is the starting point, so we go to the row for node B and look up the column for the destination node E, which says we can go straight to node E. When we look up the row for node E and its column, we get the termination condition, which says we've arrived at our destination.

A matrix such as this can be constructed in many different ways. I would recommend you look into Dijkstra's Algorithm for computing the shortest path between pairs of nodes in a graph. The solution of this algorithm can be encoded into the above transition matrix.

Cheers,

Timkin

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.