2

I want to build a labyrinth in which players can interact with others through leaving messages for one another, so in its most basic form each "tile" of the map is a forum thread or chat room.

However, I intend to have the maze continue to be generated for a very long time (the process is deterministic and will eventually terminate, but only if the 50% chance of each branch continuing fails for every single branch simultaneously. Interestingly a seed value of 42 results in a maze of size "3 tiles", so clearly 42 is not the answer here :D) and each room will have some data, such as which directions are open and which one points to the origin (can be useful for pathfinding later - find the path to the origin and they'll meet somewhere, thus you find the path between the two; this works because there are no loops, only branches).

Anyway, here's the table structure I have in mind for saving rooms:

CREATE TABLE `rooms` (
    `x` INT NOT NULL,
    `y` INT NOT NULL,
    PRIMARY KEY (`x`,`y`),
    `open_left` TINYINT(1) UNSIGNED NOT NULL,
    `open_right` TINYINT(1) UNSIGNED NOT NULL,
    `open_up` TINYINT(1) UNSIGNED NOT NULL,
    `open_down` TINYINT(1) UNSIGNED NOT NULL,
    `origin_direction` ENUM('isorigin','left','right','up','down') NOT NULL
) ENGINE=InnoDB;

Then, the chat messages can be saved like so:

CREATE TABLE `messages` (
    `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `x` INT NOT NULL,
    `y` INT NOT NULL,
    FOREIGN KEY (`x`,`y`) REFERENCES `rooms` (`x`,`y`)
        ON DELETE CASCADE ON UPDATE CASCADE,
    `timestamp` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    ...
) ENGINE=InnoDB;

This seems fine, but there's one problem I can forsee:

The maze will be absolutely massive if given enough time to be generated. Based on how it is generated, its size will be exponential and could easily reach millions, perhaps billions of rooms. And past experience has taught me, tables with millions of rows are trouble.

I imagine I will probably need to break the world down into chunks. Say, each chunk can be 1000x1000 tiles in size, giving a maximum capacity of 1,000,000 rooms (assuming somehow the maze generation fills every tile in the area). This seems simple enough, and I can procedurally create tables or even whole databases of the form zone_X_Y with X and Y being the respective coordinates of that sector.

I guess mostly this question is to voice my thought process and see if anyone has any suggestions to make for better alternatives. My DB experience is pretty much just picking up what I can as I go along and learning from past mistakes.

1
  • "tables with millions of rows are trouble" - really? Looks like most corporations and businesses who have small-medium sized databases are in trouble, then... Mar 15 '16 at 10:34
1

Use UNSIGNED to squeeze out an extra bit. A 3-byte MEDIUMINT UNSIGNED gives you 0..16M; a 4-byte INT UNSIGNED gives you 0..4 billion. Since we are talking about X and Y, what is the max width/height of the maze? 16M or 64K seems more realistic than 4B.

Consider using a TINYINT UNSIGNED or SET to handle the 4 "open" flags. That would take 1 byte instead of 4. Don't you want to go for 3 dimensions? Why not 4? Or string-theory with 10 or 11. (That would take 2 bytes for all the possible openings.)

Smaller --> faster, especially since this may become I/O bound.

Do you really need FOREIGN KEY and cascading delete?

I don't think MySQL needs for you to break it into 'chunks', but if you do, use suitably sized ints, such as the 2-byte SMALLINT UNSIGNED (0..65535).

Perhaps you are optimistic to think there will be more than 4 billion "messages"? Do you have a terabyte-sized disk?

I can't really advise on the structure, nor the indexes, without seeing the queries. I would "guess" that you always say WHERE x=... AND y=...; that is, specifying both?

Is someone (a human, that is) going to wander through this maze? Even at one 'step' per second, a human cannot realistically touch more than 10M rooms in a year. And such a person would probably need a padded cell after that.

4
  • I'm not sure I get the UNSIGNED point at the start. Since you start at the origin (0,0), coordinates can almost immediately go negative. The rest makes sense, and yes pretty much all queries will either be x = ... AND y = ..., but there may occasionally be x BETWEEN (_,_) and y BETWEEN (_,_) for things like local area search. As for the foreign key... I added it to ensure that the room exists when attempting to post messages to it, but since rooms will never be changed or deleted, what's the better option here? Mar 15 '16 at 13:00
  • OK, skip my UNSIGNED comment. +/-2 billion; +/-8M, +/-32K. "Local area search" is equivalent to "latitude/longitude", which may give you performance problems. FKs are overhead; if the code can 'never' go wrong, they aren't needed.
    – Rick James
    Mar 15 '16 at 15:35
  • I guess in this case even if code does go wrong, there's no real harm in this "orphan" post floating in void space, so just use a regular KEY for that? Mar 15 '16 at 16:50
  • Regular Keys should be added to support the important queries. Cookbook on such.
    – Rick James
    Mar 15 '16 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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