Page 1 of 1

Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 12:47 am
by Skara
I'm having a go at creating random maps. I think I've mostly got the type of map I want, but I'm having trouble with validating it. Here's a simple version of a generated map:

x = wall
. = floor (walkable) space

Code: Select all

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 0
x..............xx...............x 1
x............xxxxx..............x 2
x............xxxxx..xx..........x 3
x............xxxxxxxxxx.........x 4
x....xxx...xxxxxx.xxxxx......xx.x 5
x....xxx...xxx....xxxxx....xxxxxx 6
x....xxx...xxx.....xxxxx..xxxxxxx 7
x...................xxxxx.xxxxxxx 8
x......xx...........xxxxx.xxxxx.x 9
x......xx...........xxxxx..xxx..x 10
x....................xxxxx.xxx..x 11
x......................xxxxxxxx.x 12
x......................xxxxxxxx.x 13
x.................xx......xxxxx.x 14
x.................xx.......xxx..x 15
x...............................x 16
x..............xx...............x 17
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 18
Notice how the top-right walkable area is completely blocked off from the larger walkable area? That can't happen. I need a way to make sure you can walk from any one walkable spot to any other. You can't move diagonally.
Or, phrased differently, I need all the .'s to be one solid mass of dots. Above, there are two masses.

Has anyone done anything like this before or have any ideas on how to go about it? Thanks!

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 1:19 am
by josh
Probably going to need linear algebra, which I don't understand yet fully. You might also want to look at support vector machines and 'the kernel trick'. You could probably write code that "walked" all possible paths until all pixels were covered, but you're going to have an extremely long running time for any maps much larger then that.

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 1:40 am
by requinix
Don't think this will become a habit: I post solutions instead of advice when the problem itself interests me enough.

Code: Select all

<?php
 
header("Content-Type: text/plain");
 
$spaces = array(//         vv -------------------+
    0 => 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx', // |
    1 => 'x..............xx...............x', // |
    2 => 'x............xxxxx..............x', // |
    3 => 'x............xxxxx..xx..........x', // |
    4 => 'x............xxxxxxxxxx.........x', // < mark those tiles as '.' for the opposite result
    5 => 'x....xxx...xxxxxx.xxxxx......xx.x',
    6 => 'x....xxx...xxx....xxxxx....xxxxxx',
    7 => 'x....xxx...xxx.....xxxxx..xxxxxxx',
    8 => 'x...................xxxxx.xxxxxxx',
    9 => 'x......xx...........xxxxx.xxxxx.x',
    10=> 'x......xx...........xxxxx..xxx..x',
    11=> 'x....................xxxxx.xxx..x',
    12=> 'x......................xxxxxxxx.x',
    13=> 'x......................xxxxxxxx.x',
    14=> 'x.................xx......xxxxx.x',
    15=> 'x.................xx.......xxx..x',
    16=> 'x...............................x',
    17=> 'x..............xx...............x',
    18=> 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
);
$width = 33; $height = 19; // dimensions
 
// start here
 
$copy = $spaces;  // copy of the array (we'll be modifying it later)
$tiles = array(); // tiles to examine
 
// find a starting location: first open tile
for ($i = 0; $i < $height; $i++) for ($j = 0; $j < $width; $j++) {
    $tile = $copy[$i][$j];
    if ($tile == '.') { $tiles[] = array($j, $i); break 2; }
}
 
// scan each tile in our list looking for open neighbors
for ($i = 0; $i < count($tiles); $i++) {
    list($x, $y) = $tiles[$i];
    
    if ($y > 0 && $copy[$y-1][$x] == '.') { // if we aren't off the map AND it's an open tile
        $tiles[] = array($x, $y-1); // add this location to the list of tiles to scan
        $copy[$y-1][$x] = ' '; // mark this tile as not-open
    }
    if ($x < $width && $copy[$y][$x+1] == '.') { $tiles[] = array($x+1, $y); $copy[$y][$x+1] = ' '; }
    if ($y < $height && $copy[$y+1][$x] == '.') { $tiles[] = array($x, $y+1); $copy[$y+1][$x] = ' '; }
    if ($x > 0 && $copy[$y][$x-1] == '.') { $tiles[] = array($x-1, $y); $copy[$y][$x-1] = ' '; }    
}
 
// done - look for remaining open tiles
for ($i = 0; $i < $height; $i++) for ($j = 0; $j < $width; $j++) {
    if ($copy[$i][$j] == '.') {
        echo "Unreachable tiles found\n\n";
        for ($i = 0; $i < $height; $i++) echo $copy[$i], "\n"; // print out the map (for testing purposes)
        return;
    }
}
 
echo "All open files reachable\n";
It's the quick-n-dirty solution but it runs very fast: for the map you posted, a bit over 3000 ticks.

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 2:16 am
by Skara
Wow. That's actually really elegant. Thanks. Works like a charm. I now have random maps implemented! :D

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 2:57 am
by josh
What algorithm is that based on? Or did you just sorted through the logic? I half follow it, I'll take your word that it works though... lol

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 5:50 am
by requinix
jshpro2 wrote:What algorithm is that based on? Or did you just sorted through the logic? I half follow it, I'll take your word that it works though... lol
(whoops, three hours later...)

Basically it picks a point to start from, finds the neighbors which aren't walls, rinses, and repeats. (Neighbors which get added to the processing queue get marked off so they aren't used again.)
After the queue is empty it looks for an unmarked floor: if there is one the map is bad, otherwise the map is good.

If you could travel diagonally the algorithm would stay the same except there would be four more neighbors to look at.

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 8:32 am
by Mark Baker
Out of interest, is that using Dijkstra BFS, or A-Star, or some other variant?

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 3:04 pm
by josh
To restate what it is doing in simpler terms, I think he means it loops through all the tiles.. it finds the first open tile, then it starts "walking" in every direction, it goes thru the nested loops "crawling" north south east and west, after its covered as much ground as it can it does another loop which loops thru the whole map, and if it finds open tiles it did not cover during the 1st nested loop, it knows they are impossible to reach. This works fine for a 100 x 100 map or so but I'd be interested in how you would solve this problem for a huge RPG or FPS where the map is much larger, and more involved checks need to be done, like where the terain is dynamic.

Thanks for explaining the logic. FYI this is more of a "brute force" then an algorithm since it tries every possible combination, it is still very clever though

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 8:38 pm
by requinix
jshpro2 wrote:To restate what it is doing in simpler terms, I think she means it loops through all the tiles.. it finds the first open tile, then it starts "walking" in every direction, it goes thru the nested loops "crawling" north south east and west, after its covered as much ground as it can it does another loop which loops thru the whole map, and if it finds open tiles it did not cover during the 1st nested loop, it knows they are impossible to reach. This works fine for a 100 x 100 map or so but I'd be interested in how you would solve this problem for a huge RPG or FPS where the map is much larger, and more involved checks need to be done, like where the terain is dynamic.

Thanks for explaining the logic. FYI this is more of a "brute force" then an algorithm since it tries every possible combination, it is still very clever though
Like I said, it was the easy solution for dealing with a small, simple map.

How large is "much larger", and what kind of "involved checks" are you talking about?

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 9:00 pm
by josh
Hmm I don't know I'm just wondering if there's some algorithm that can give you a yes / no answer using some math formula, if you could identify the edges of the walled in areas you could do a collision check. I give you respect for actually coming up with the code, I'm just wondering if there's ways to do it mathematically, most modern games still use "grids" to represent the map but the in-game player has such a fine amount of control over movements I could picture there already being a algorithm for this

Re: Random Maps - Contiguous Ground Area

Posted: Sun Dec 28, 2008 10:31 pm
by requinix
Most algorithms would have to be involved (at least partly) in the construction of the map, not just during a validation stage.
Without any information already collected about the map the algorithm has to find the various landmasses itself which is a large part of what my code had to do. Once those groups have been identified the collision detection is simple enough; that would have been less efficient for mine, though, because by the time the identification is done the algorithm could have a conclusion.

Re: Random Maps - Contiguous Ground Area

Posted: Mon Dec 29, 2008 12:56 am
by josh
Yeah, ideally you want to avoid trial and error type stuff, if you can prevent from generating invalid stuff that is generally a good idea.. unless you're validating user generated maps or something...