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?

However, as I use a database as the source of all my game info storage,

Why?

Databases are a tradeoff. Does your game benefit from the pros of a database more than it suffers from the cons?

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

Have you calculated how much information it'll actually take?

i.e. How many rooms do you actually have? How many connections do you actually need per room? How much memory does each connection take?

Let's do some back-of-the-napkin estimates here.
I'm gonna guess you have less than a million rooms.
I'm gonna guess that each room has an average of 2.5 connections to other rooms.

I'm gonna assume you are giving each room a unique ID, and that that ID can fit into a 32 bit variable (maybe even 16 or 24 bits).
I'm gonna assume your 'connection' can be just be the ID of the room you are connecting to, and, maybe 32 bits of additional info (i.e. locked/unlocked, or whatever else). That's 8 bytes per connection.

(1 million rooms * 2.5 connects * 8 bytes per connection) = 20,000,000 bytes = 19,531~ KB = 19~ MB = not worth bothering about. You can keep that all in RAM, no problem. Is there some other consideration that makes this not an option?

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.

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.

That seems to be root of your issue. You've chosen solution first, then you've built problem around it. Choosing low level storage should be the last step after you know what your objects look like, what connections (I intentionally avoid the word "relations" here) look like. How do you need to access them and what is size of all of this.

Then you can take educated decision what storage to use. Is fully fleshed SQL database the right tool? Many non-SQL database is better? Or maybe plain file is the best?

This is the same for every aspect of any program. You first need to know WHAT do you want, then you decide HOW to do it.

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!

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.

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!

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