Sign in to follow this  

Pathfinding and Databases

This topic is 728 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working my way through Programming Game AI by Example, and have come upon the section on graphs and pathfinding.  Now, my game has a very simple grid layout for each room: a simple 3 x 3.  I'm looking at this graph node and edge chapter and thinking, 'Cool, this should solve my pathfinding problems fairly well!'  However, as I use a database as the source of all my game info storage, and my MUD has a huge number of rooms, storing all those nodes and edges and such in a database seems like such a HUGE amount of information, and I've come to wonder if this is the proper way to go.  Any thoughts on my room layout and a good, efficient way to store and search the room for adequate paths?

Share this post


Link to post
Share on other sites

Are we talking pathfinding within rooms, or between rooms? I'm guessing between rooms, because pathfinding in a 3x3 grid is pretty trivial and you could basically brute-force it, try all permutations, and still perform pretty well.

 

I think the problem you're having is that the way you store your room layout (in a database) isn't really conducive to most path-finding algorithms, which assume that it's easy to load and traverse every node in the graph, right?

 

You've probably got a couple of options here:

  1. Limit the number of rooms you search, which limits how many rooms you're going to have to load. You're going to have a bunch of rooms in memory already to display them to the user, as a first pass you could just limit your path finding to whatever you've already got loaded. The downside here is that you might not find a path which twists through rooms that are not loaded.
  2. Pre-calculate some fraction of possible paths when you generate the level. This could potentially mean you have a whole lot more data to store.
  3. Some other data structure/storage mechanism for your level (e.g. a quadtree). This could be a lot of work...

As always, there's never a perfect solution.

Share this post


Link to post
Share on other sites
I guess what the experts think is trivial and what I think is trivial are two completely different things lol!

And, to clarify, I am talking about storing edges and nodes for traversing WITHIN rooms, not between. From what I can tell, that's 9 nodes per room, with 16 edges. If I got crazy, I would also need to store directional info for each edge and weights (though I might be able to combine these last two I think). Just thinking about the amount of fields in that relational table makes me cringe hahah. But, mayhap I am overthinking things.

As for why I'm using a database question, well, I understand databases and have designed my game around an entity/component structure. This maps quite well to my database.

I think, at the root of it, is the lack of any real knowledge of just how much memory I'm going to be using. I've included quite a few little things, call them game experience enhancements, that I'm worried will just bog down the system. Servant, you talk about connections between rooms being quite low in memory usage, but my connections are their own components that store not only the room it connects to, but what feature it goes through, what space in the next room you arrive at, and the description you read from passing into the connection and the description you read from coming out the other side. I do this a lot in different areas to add depth to the game.

I think I'm just worried about the capability of my system to perform, and as I've already had to do one complete rebuild when I realized the current design wouldn't fit my needs, I'm dreading getting too deep in a certain design before realizing it won't work.

Thanks again for your input.

After some napkin math, I realize I'm probably just being over cautious.

Share this post


Link to post
Share on other sites
The problem is, when you are learning by doing, it is often impossible to know what you need until you've built a large amount of code that works, and then move on to a new aspect. I wouldn't call it a problem, as for the large majority of my game, my database works perfectly. Unfortunately, I don't know enough about path finding to know how it's handled in large games or games of my type, so finding good solutions aren't quite as obvious to me yet. That being said, I'm slowly learning to adapt my understanding of database design and program design to make the two mesh quite nicely. I will say that I did my research going in, and for my design, at least for the part I could predict I needed, a database was a good solution. Thanks for the feedback!

Share this post


Link to post
Share on other sites

I wouldn't call it a problem, as for the large majority of my game, my database works perfectly.

 

Databases, as in relational databases with a server like MySQL or SqlServer or Oracle, generally have a minimum response time around 10 milliseconds.

 

Video games often have frame rates around 1/60 or 1/75 or 1/100 of a second.

 

It is not a matter of the tool not functioning.  The functionality can be present.  The problem is that the tool is generally far to slow for the job you are describing.  You can use the database to store broad information for persistence where you save and load big pieces of information, but in doing so you transfer them over to your game and work with them as a working set of data.

 

I don't know enough about path finding to know how it's handled in large games or games of my type, so finding good solutions aren't quite as obvious to me yet.

Typically a small spatial tree or navigation mesh is loaded. It may have a few hundred or many thousand nodes.

 

A pathfinding request first converts the source and destination coordinates into navigation mesh node IDs.  For example, you may be trying to get from node 721 to node 436.

 

Then a pathfinding routine like A* ("A Star") is used. Before the A* algorithm, Dijkstra's shortest path algorithm was common. A* is Dijkstra's algorithm plus a heuristic that lets you give preference to results you know are closer to the destination, and in the worst case or when the heuristic is turned off A* is equivalent to Dijkstra's algorithm.  

 

Then the turns and twists on the navigation mesh nodes are converted back to world coordinates, and used to move your characters in the game.

Share this post


Link to post
Share on other sites

Databases, as in relational databases with a server like MySQL or SqlServer or Oracle, generally have a minimum response time around 10 milliseconds.


Video games often have frame rates around 1/60 or 1/75 or 1/100 of a second.


It is not a matter of the tool not functioning. The functionality can be present. The problem is that the tool is generally far to slow for the job you are describing. You can use the database to store broad information for persistence where you save and load big pieces of information, but in doing so you transfer them over to your game and work with them as a working set of data.

 

I've made this discovery myself. I don't access the database directly often.  I separated my MUD out into many specific zones, which are only loaded into memory when a player enters them, and unloaded after a short period of time after the game detects that no players are present within them.  A zone is loaded and unloaded asynchronously so as not to interrupt the game flow.  I had assumed that, as part of that loading process, I would be loading a number of nodes and edges into each room in order to establish a navimap, but upon looking at that problem closely, I felt like the sheer number of nodes and edges necessary would quickly bloat the memory usage of each zone to huge levels, not to mention the absolutely massive table necessary to hold all those nodes and edges.  However, after reading everyone's responses, I think I'm just being too conservative, and my problem really isn't something to worry about.  I could be wrong, but honestly, I don't see how I will REALLY know until I implement it.  I would, however, enjoy seeing how navimeshes and the like are stored in a database for MMORPG's, as that would probably mirror my setup the closest.  Thanks again!

Edited by Theis_Bane

Share this post


Link to post
Share on other sites
Just to add a bit to the pile-on: a common problem for novices is learning to differentiate what they think is a huge amount of memory usage from what the computer thinks is a huge amount. It sounds like you might be making a text-based MUD. In terms relative to modern RAM capacity, such a thing is extremely light-weight. On modern multi-gigabyte systems, you could likely have hundreds of thousands, if not millions, of rooms resident in RAM. I'd posit that you could at least have as many rooms loaded as you could conceivably create and flesh-out within the next five years or more, barring large-scale procedural generation.

I can remember working on MUDS in the 90s that had hundreds of rooms, took many hours to explore, and could be held entirely within the paltry RAM capacities of the day. Imagine how much you can do now.

Share this post


Link to post
Share on other sites

Just to add a bit to the pile-on: a common problem for novices is learning to differentiate what they think is a huge amount of memory usage from what the computer thinks is a huge amount. It sounds like you might be making a text-based MUD. In terms relative to modern RAM capacity, such a thing is extremely light-weight. On modern multi-gigabyte systems, you could likely have hundreds of thousands, if not millions, of rooms resident in RAM. I'd posit that you could at least have as many rooms loaded as you could conceivably create and flesh-out within the next five years or more, barring large-scale procedural generation.

I can remember working on MUDS in the 90s that had hundreds of rooms, took many hours to explore, and could be held entirely within the paltry RAM capacities of the day. Imagine how much you can do now.

 

I think this is my issue.  With all the 'quality of life' improvements I feel like I've made, it just seems like SO MUCH, to the point that I'm becoming worried it just won't run fast enough to be playable.  But...I don't know what I'm talking about in this regard so maybe I should just shut up and build it lol

Share this post


Link to post
Share on other sites

If the room is 3x3 and has 16 edges then just move toward the goal in a straight line. There's no need for any complication. Pathfinding is only necessary when there are obstructions.

 

Incidentally, four more edges would complete that graph quite nicely.

Edited by Khatharr

Share this post


Link to post
Share on other sites

I would, however, enjoy seeing how navimeshes and the like are stored in a database for MMORPG's, as that would probably mirror my setup the closest.



No serious (read: shipped) MMO would store navmesh data in a relational database format. What you will typically find is some kind of custom binary format that describes a compact data structure. Most of the time that data is just read directly into RAM, potentially with some fixups for pointer addresses, and used from there.

MMO servers typically have many GB of RAM available and sometimes even use a good chunk of it for caching and precomputation purposes. RAM is cheap and computers are fast. If you don't have profiling data to prove your performance assumptions, then those assumptions are worthless, period. It doesn't matter if you're new to game programming or have been doing it since the punch card era; I don't care what your intuition says, unless you've benchmarked the exact use case in question, you're probably wrong. There's a good chance you're dramatically wrong.

As has also been touched on, some data is not relational by nature and storing it in a relational DB is just unwise at best. It isn't really a performance or efficiency concern in my mind, though. It's an appropriateness of abstraction concern. The more you cram into your DB without reason, the more awkward things are going to get.

Trust your gut. Your gut says it would suck to store your navigation data in your database. So listen.

Share this post


Link to post
Share on other sites


MMO servers typically have many GB of RAM available and sometimes even use a good chunk of it for caching and precomputation purposes. RAM is cheap and computers are fast. If you don't have profiling data to prove your performance assumptions, then those assumptions are worthless, period. It doesn't matter if you're new to game programming or have been doing it since the punch card era; I don't care what your intuition says, unless you've benchmarked the exact use case in question, you're probably wrong. There's a good chance you're dramatically wrong.

 

To add to this, MMO servers are also typically highly partitioned.  Even for huge AAA projects, they don't have the world on one box (well, they probably do, but it's on-disk), but a small piece of it.  Working at a MMO developer, RAM has never been our bottleneck.  Typically it's either the database or some abstraction on top of the database.

 

But that's all a moot point when talking about a MUD, which is orders of magnitude different.

Share this post


Link to post
Share on other sites

 

I would, however, enjoy seeing how navimeshes and the like are stored in a database for MMORPG's, as that would probably mirror my setup the closest.

No serious (read: shipped) MMO would store navmesh data in a relational database format. What you will typically find is some kind of custom binary format that describes a compact data structure. Most of the time that data is just read directly into RAM, potentially with some fixups for pointer addresses, and used from there.MMO servers typically have many GB of RAM available and sometimes even use a good chunk of it for caching and precomputation purposes. RAM is cheap and computers are fast. If you don't have profiling data to prove your performance assumptions, then those assumptions are worthless, period. It doesn't matter if you're new to game programming or have been doing it since the punch card era; I don't care what your intuition says, unless you've benchmarked the exact use case in question, you're probably wrong. There's a good chance you're dramatically wrong.As has also been touched on, some data is not relational by nature and storing it in a relational DB is just unwise at best. It isn't really a performance or efficiency concern in my mind, though. It's an appropriateness of abstraction concern. The more you cram into your DB without reason, the more awkward things are going to get.Trust your gut. Your gut says it would suck to store your navigation data in your database. So listen.

EDIT - Reread after I've had some sleep, and now I feel silly.  Leaving the below as a reminder to myself to stop and think.  Thanks to everyone.

 

Alright, the tone of this response irked me, so I apologize in advance if I come across harsh.

I'm not discussing ram. I understand that part. The vast majority of my game runs in ram. The database is only used for persistence. What I'm asking about is persisting navigational data. I can only work with what I know, and what I know is databases. I literally can not speak to any other method of storage when it comes to this because I'm not fully aware how it would work. If you have another suggestion, great. I would love to hear about it and learn. That's why I'm here.

Not to mention the fact that I've already admitted to not really knowing the performance outcome, and believing im being overly conservative. I feel like, had you read my posts, you would have seen that.

I apologize if I'm reading too much into this, but I read it six times and am having a hard time seeing this any other way.
 

If the room is 3x3 and has 16 edges then just move toward the goal in a straight line. There's no need for any complication. Pathfinding is only necessary when there are obstructions.

Incidentally, four more edges would complete that graph quite nicely.

There will be the possibility for obstructions, so I will need to account for that. I am curious though, where are the other four edges coming from? I only count 16.


All this being said, I think I'm going to build a static navigraph class with nodes and edges preloaded, as all the rooms are generically shaped. This will allow me to plan a route with very little extra data needed to be stored. I will use my entities to shape the room how I see fit, like placing a 'hole' entity in a square and making it take up the whole square, so that the square appears blocked when i try to path. Thank you everyone for your time. You've helped more than you know!

Edited by Theis_Bane

Share this post


Link to post
Share on other sites

 

I am curious though, where are the other four edges coming from? I only count 16.

Entries and exits of the room.

Ah. I figured that may be what you meant. However, in my game, I would potentially need nine more edges on enclosed rooms, and.... A whole lot more on open terrain. I did that so you could have multiple doors on one wall, allowing players to enter and exit a room from multiple spots.

Mad props on that graphic though.

 

EDIT - Holy crap!  I just found the other four edges INSIDE the room.  Blind as a bat...Thanks!

Edited by Theis_Bane

Share this post


Link to post
Share on other sites

The database is only used for persistence. What I'm asking about is persisting navigational data.


This is totally unclear from your posts, unfortunately.

There are two basic situations in which you would use persistent navigational data:

- Static geometry
- Dynamic geometry


In the former case, you will only need to load the data once and then never modify it or otherwise do anything with it besides searches. This is the optimal case for using a simple data structure that is serialized to disk at build time, and then loaded at runtime once and used indefinitely for navigation queries. That's the solution most games have because most games don't need much in the way of truly dynamic navigation.

For the record, you can fake dynamic navigation in a method similar to what you suggested yourself: store the "fully connected" world in memory, and simply score some edges of the navigation graph as impassable if the situation calls for it. An example would be a door that is only big enough for hobbits to crawl through. If an ogre makes a navigation search, he can use the exact same navigation data as the hobbit, but the ogre's score for the door will be impassable/blocked whereas the hobbit will perceive an edge that he can traverse.


Truly dynamic navigation is another beast and based on the logical assumptions most people would make from the thread, it isn't something you actually need. You haven't described any design goals that specifically require it. However, the typical solution is to store a hierarchical navigation data structure: one structure per "room" or "area" or whatever, and another high-level structure that describes how those smaller elements interconnect. When the navigation structure of the world changes, you simply rebuild the data structure for the affected regions. The hierarchical approach helps limit the knock-on effects of localized changes.


Note that both approaches involve custom data structures (graphs or navmeshes usually) and no relational DBs at all. Persistence does not inherently imply storage in a relational DB, that's all I was trying to say :-)



I can only work with what I know, and what I know is databases. I literally can not speak to any other method of storage when it comes to this because I'm not fully aware how it would work. If you have another suggestion, great. I would love to hear about it and learn. That's why I'm here.


I've described better solutions as has almost every other post in the thread. I responded because you were still talking about relational DBs even after all the suggested superior alternatives were available for you to analyze on your own. Also because I work on an MMORPG and I wanted to correct a misconception that we use relational data for navigation.

Nobody's asking you to speak to anything you don't know. We're giving you options to learn about and broaden your skill sets. If you don't know the tools for the job, learn them! There's nothing wrong with that and no reason to feel slighted by being told that you're missing a useful piece of knowledge.


Not to mention the fact that I've already admitted to not really knowing the performance outcome, and believing im being overly conservative. I feel like, had you read my posts, you would have seen that.


As I explicitly said, I don't even think performance is the real problem with relational DBs for this situation. I think the misuse of the tool is far more important on a conceptual level than a speed level. I remarked on performance merely for cohesion with the rest of the discussion but my real point was here:

It isn't really a performance or efficiency concern in my mind, though. It's an appropriateness of abstraction concern. The more you cram into your DB without reason, the more awkward things are going to get.

Trust your gut. Your gut says it would suck to store your navigation data in your database. So listen.



Anyways, I'm sorry if that all came off as a bit harsh or insensitive. I think we were simply operating under different sets of assumptions about what the subject of the thread is and where things stand with regards to finding a solution.

Share this post


Link to post
Share on other sites

No, no.  It's not problem.  I was a bit tired last night when I wrote that.  Woke up this morning and reread what I and you wrote and was sort of like....eh?  Didn't want to just delete it as I wasn't sure if it had been read.

 

As for the above, that makes sense.  Didn't realize I wasn't clear about loading my database into memory for calculation purposes.  Sorry about that.

 

I think I've probably got this figured out now.  Again, thank you for your time.  Apologies again for MY tone.  Back to the grind!

Share this post


Link to post
Share on other sites
Sign in to follow this