Jump to content
  • Advertisement
Sign in to follow this  
Theis_Bane

Pathfinding and Databases

This topic is 1059 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
Advertisement

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!