2

Note: I am using MySQL 5.5.36.

I'm working on a game design feature for a game that has rooms but does not have coordinates or relationships with other rooms in any way except exits. I've created a fiddle to illustrate a tiny snip of the data:

https://dbfiddle.uk/?rdbms=mysql_5.5&fiddle=9d4ebc91e10a67e187fb4a4b623728da

So in real application, I may be trying to connect a room to another room dozens of hops or more away. I'm not sure how I can best use the data I have to find a path from room A to room Z.

Rich
  • 63
  • 1
  • 1
  • 6
  • Read about recursive CTEs in MySQL, if you are using MySQL 8+. – Tim Biegeleisen Dec 07 '20 at 04:58
  • Sadly, I am using MySQL 5.5.36 and I'm not sure if upgrading is an option. – Rich Dec 07 '20 at 05:52
  • There are workarounds. Search SO for "recursive hierarchical query MySQL" – Tim Biegeleisen Dec 07 '20 at 05:54
  • I assume the relation between `room_num` and `target_room` columns are many-to-many? – FanoFN Dec 07 '20 at 05:54
  • Each room_num is likely to connect to many target_room values, each a row in the table. – Rich Dec 07 '20 at 05:55
  • I should add that it is possible for me to add another column to the table that would contain every room a room connects to, or instead of many rows for a given room, i could change it so it's one row and target_room becomes target_rooms with a value of all rooms directly connected i.e. (#444,#141,#888) – Rich Dec 07 '20 at 05:59
  • I have created a fiddle example here : https://dbfiddle.uk/?rdbms=mysql_5.5&fiddle=88da05df2019464e0a0d3cfdb4e42bc6 . Can you please edit it accordingly and insert an example query that you have tried inside. Once you finished, just click "Run" and the fiddle will generate a new link. Post that new link into your question. Thanks – FanoFN Dec 07 '20 at 06:02
  • I'm not sure what you're asking me to do, I'm afraid. I don't really have an example of anything I've done because I'm at a loss for where to begin. Also, note that I gave the example of rooms A->B->C->D->E just to illustrate, I have no idea what a correct path from A to E would be. I just know I have a table with 28734 rows of parent to child relationships and I'm trying to establish a relationship between what could in some cases be a descendant to ancestor dozens of parent relationships past. – Rich Dec 07 '20 at 06:09
  • Ok, there's no need to be afraid. A fiddle is just an online rdbms made available for us to create a [minimal, reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). You said you're on MySQL 5.5 correct? So [this fiddle](https://dbfiddle.uk/?rdbms=mysql_5.5&fiddle=88da05df2019464e0a0d3cfdb4e42bc6) version is exactly 5.5 and you just have to create (or insert) the table similar to what you're working with. Just a fake data (5 to 10 rows) will do as long as it can replicate your situation. – FanoFN Dec 07 '20 at 06:33
  • OK, I did this though I'm not sure what to do with it. It's fake data since my real data is over 22,000 rows. https://dbfiddle.uk/?rdbms=mysql_5.5&fiddle=cd39b782a665fec703c7091aae5d2cab – Rich Dec 07 '20 at 06:44
  • Are those rooms changing (e.g. do users randomly add rooms/connections)? If not, by all means, do precalculate those connected graphs. If they change, think about recalculating them when you change them. If that isn't an option: change your data model (see tims search terms for a thread with suggestions); a linked list is about the worst possible data model for MySQL 5.5 for your situation. Or really update to MySQL 8 (although you maybe should still precalcuate them there too depending on what the rooms do, but if you don't, at least it can handle the linked list model). – Solarflare Dec 07 '20 at 08:47
  • The rooms change very infrequently. I'll work on changing the table so it's one room tied to a list of connections. I'm not sure what to do after that but I can at least get it in place and make a new fiddle. Thank you. – Rich Dec 07 '20 at 14:05
  • I've modified the question above to reflect a change to the table structure and data. – Rich Dec 07 '20 at 23:23

1 Answers1

0

Here's an idea:

SET @room := 555; -- setting variable for first room
SET @troom := 123; -- setting variable for last room

SELECT r1.room_num, r1.target_room, r2.target_room, r3.target_room, r4.target_room, r5.target_room, r6.target_room, r7.target_room
FROM room_map r1 
JOIN room_map r2 ON r1.target_room=r2.room_num
JOIN room_map r3 ON r2.target_room=r3.room_num
JOIN room_map r4 ON r3.target_room=r4.room_num
JOIN room_map r5 ON r4.target_room=r5.room_num
JOIN room_map r6 ON r5.target_room=r6.room_num
JOIN room_map r7 ON r6.target_room=r7.room_num
WHERE r1.room_num=@room -- using first room variable
AND r7.target_room=@troom -- using last room variable ;

In this fiddle: https://dbfiddle.uk/?rdbms=mysql_5.5&fiddle=6fb252fbc9495a34480e3f11175fad3e

This query will give you 3 rows as result - matching first and last room number condition. That is because you have a many-to-many relationship between the columns. What's next is for you to try on this query - add conditions that is feasible for your needs and update your question with new details/findings.

Also, see if this might help.

FanoFN
  • 6,815
  • 2
  • 13
  • 33
  • I did try something like that earlier (different but essentially the same thing). The problem is that I don't know how deeply nested the needle is that I'm looking for but if I were going to set a reasonable maximum nesting, it would be at least 30, preferably 50 or more. Once I got beyond about 12 levels, the query started really slowing down. – Rich Dec 07 '20 at 07:42
  • Maybe the approach to load all of the connected rooms in one single query is not the best way? How is the game flow? Can each of the room be attached with one single query that only find the current `room_num` with its `target_room`? On a loop? – FanoFN Dec 07 '20 at 08:01
  • Well, these rooms don't change often so what I do have the luxury of doing is running certain queries ahead of time that don't need to be redone often. So for example, I can redesign the table so instead of room_num and target_room it's room_num and then a list of directly connected rooms in target_rooms or something. Like if room 555 connects to 444, 13 and 29 then maybe only one row for 555 which looks like room_num 555, target rooms 444,13,29 or whatever format is needed. – Rich Dec 07 '20 at 08:08
  • I've modified the question above to reflect a change to the table structure and data. – Rich Dec 07 '20 at 23:23