Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm trying to figure out how to do what I can only call a recursive query (my knowledge of MySQL is extremely limited). The game I'm designing has a tech tree with items to research that will grant you stronger stuff down the line. The prerequisites are broken down in another table, since each tech item can have 0 or more prereqs.

CREATE  TABLE IF NOT EXISTS `tech` (
  `id` INT NOT NULL ,
  `name` VARCHAR(45) NULL DEFAULT NULL ,
  PRIMARY KEY (`id`) );
CREATE  TABLE IF NOT EXISTS `prereq` (
  `src_id` INT NOT NULL ,
  `prereq_id` INT NOT NULL );
INSERT INTO tech (`id`,`name`) VALUES(1001, 'Logic');
INSERT INTO tech (`id`,`name`) VALUES(1002, 'Classical Physics');
INSERT INTO tech (`id`,`name`) VALUES(1005, 'Global Economics');
INSERT INTO tech (`id`,`name`) VALUES(1008, 'Solar Power Collector');
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1008,1005);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1005,1001);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1005,1002);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1001,NULL);
INSERT INTO prereq (`src_id`,`prereq_id`) VALUES (1002,NULL);

With this set up, I can query the tables and find that if I want solar power, I need to first research Global Economics:

SELECT t.name, t.id, GROUP_CONCAT(p.prereq_id ORDER BY p.prereq_id ASC)
FROM tech t LEFT JOIN prereq p on t.id=p.src_id
WHERE t.id=1008
GROUP BY t.name, t.id
ORDER BY t.id

What I'm trying to get at is a result set that include the next level of prerequisites, then the next, until we hit nodes that have NULL. So I'm looking for this:

id     name
1008   Solar Power Collector
1005   Global Economics
1001   Logic
1002   Classical Physics

Is this even possible within MySQL? I tried to use a cursor, but was unsuccessful. I could handle this within the actual code, but I'd rather it be done server side somehow.

Any help in pointing me in the right direction would be greatly appreciated!

share|improve this question
    
I know this is for a game but this may be better suited to StackOverflow. Also, FWIW, I think you should query everything and put it in a tree structure on the application side. –  Richard Marskell - Drackir Oct 25 '11 at 20:41
1  
I don't think this is very helpful answer, but: DON'T USE A DATABASE FOR YOUR TECH TREE! And any other static design data for that matter. –  Nevermind Oct 26 '11 at 4:11
    
@Nevermind On the contrary, while it's not really an answer I'd say it could prove extremely helpful. –  eBusiness Oct 26 '11 at 12:48
    
@eBusiness That would be nice, but usually, when such questions arise, the database usage is already set in stone. Shame really. –  Nevermind Oct 26 '11 at 13:21
1  
@Dan Champagne I don't suggest hardcoding them. Use config files. XML, JSON, YAML, or whatever format you have most experience working with, and/or best library. That's far more flexible, and supports source control to boot. –  Nevermind Oct 27 '11 at 4:18

3 Answers 3

up vote 2 down vote accepted

In postgreSQL or MS SQL Server, you'd use a recursive CTE for this.

Since MySQL doesn't support recursive CTEs, you'll have to change the structure of your table to use nested sets, or you could use as many self-joins as the depth of your tech tree. See this article http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/ for how to do it.

However, there are quite a few drawbacks to doing this kind of operation in MySQL (nested sets are really slow to insert into, the Spatial index requires a table-lock), so you should consider calculating the depencies outside of MySQL if at all possible.

share|improve this answer
    
It's a shame that MySQL doesn't support this. It looks like it would solve the problem. –  Dan Champagne Oct 26 '11 at 22:14
1  
yeah, I love recursive CTEs. With recursion and enough tolerance for pain, anything is possible. thedailywtf.com/Articles/… –  Jimmy Oct 26 '11 at 22:50
    
you might also like this: explainextended.com/2011/12/31/happy-new-year-3 –  Quassnoi Apr 1 '12 at 8:54

Seeing the discussion in comments, I guess I'd better put my recommendations as an answer.

See, I've used relational databases for all kinds of static data in the past. And it always lead to shenanigans like these. This question or this one have to deal with this too.

Relational databases are really quite inflexible in terms of data representation. Usually, you trade this flexibility for efficient storage and, first and foremost, efficient querying of large datasets.

Static game data is almost always very small, and fits easily in memory. And you very rarely need to query it in the way databases support. 99% of the time you just need the "give me object with this Id" request, and using RDBMS for it is overkill. 1% of the time, you have some crazy recursive query that becomes needlessly complex and slow, and an ugly hack.

On the other hand, static data tends to have complex schemata, lots of optional values, tree-like structure, etc. This is hard to represent efficiently in a database. Changing a database schema is also a pain usually. Lastly, you cannot put your database under source control - and you WANT your static data under source control.

So in the end, database does not give you any advantages. A better way is to store everything in config files: XML, JSON, YAML - anything goes, if you have/can develop a good library to work with the format. Config files can be put under source control, can be easily extended, and are not bound by a rigid schema. With some libs, like LINQ2XML, you can even run queries against them, just like with a DB. Config files are also human-readable and human-editable, which might come in handy. Of course, at runtime these files are read, parsed and stored in memory, using whatever data structure you want (and a simple hash table will be a billion times faster than a database query). Then your server works with this in-memory representation.

The only time when you can't do that is when you don't actually have a server, and your clients call DB directly. But then you have much, much worse problems than this (-8

share|improve this answer
    
I half concur, half disagree. A relational database offers some serious benefits when it comes to fast and complex querying of large data sets, and sometimes you do have such data for your game - especially for modern online games. However, they're not at all suited for any hierarchical data, and a format like XML/YAML/JSON is better there - just a shame the search capability for such formats is significantly reduced by comparison to SQL. –  Kylotan Oct 27 '11 at 9:08
    
WoW, arguably the largest game there is, has on the order of tens of thousands items, mobs etc. While this is quite large dataset for a human to process, it's not that large for a database. For designer working with these data, having them in a database of sorts (not necessarily relational) is probably useful. But at runtime, I think, having them all in memory is still better. –  Nevermind Oct 27 '11 at 16:59

Relational databases aren't suited to tree representations for precisely this reason. I advise you to just do this iteratively, in whatever code is using this SQL.

Note that you also have to specify how you want to traverse the tree, which isn't clear from your question. Your example has an ambiguous ordering as there either Logic or Classical Physics could go last - this will matter more when you have a bigger tree, and some of the nodes with no prerequisites might exist at different levels - should they all appear at the bottom, or should they appear some way through the structure depending on which options they make available?

Although, I second Nevermind's comment about this being the wrong data storage approach for static data. An in-memory structure would be faster and easier to process.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.