Random Maps - Contiguous Ground Area

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
Skara
Forum Regular
Posts: 703
Joined: Sat Mar 12, 2005 7:13 pm
Location: US

Random Maps - Contiguous Ground Area

Post 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!
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Random Maps - Contiguous Ground Area

Post 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.
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: Random Maps - Contiguous Ground Area

Post 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.
User avatar
Skara
Forum Regular
Posts: 703
Joined: Sat Mar 12, 2005 7:13 pm
Location: US

Re: Random Maps - Contiguous Ground Area

Post by Skara »

Wow. That's actually really elegant. Thanks. Works like a charm. I now have random maps implemented! :D
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Random Maps - Contiguous Ground Area

Post 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
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: Random Maps - Contiguous Ground Area

Post 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.
Mark Baker
Forum Regular
Posts: 710
Joined: Thu Oct 30, 2008 6:24 pm

Re: Random Maps - Contiguous Ground Area

Post by Mark Baker »

Out of interest, is that using Dijkstra BFS, or A-Star, or some other variant?
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Random Maps - Contiguous Ground Area

Post 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
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: Random Maps - Contiguous Ground Area

Post 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?
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Random Maps - Contiguous Ground Area

Post 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
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: Random Maps - Contiguous Ground Area

Post 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.
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Random Maps - Contiguous Ground Area

Post 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...
Post Reply