Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

To make this clear from the get go;

I'm not looking for HOW To randomly generate a terrain (I know I can use Perlins noise for that).

I'm looking for an algorithm that can help with the terrain generation.

Example;

Me and my friend are working on a flash game to be use as advertisement for an upcoming game (And to see if theres actually interest for the base game).

And I've been working on randomly making terrains, however! When i generate the map, i have no idea how to make it so it connects properly.

The map is isometric and tilebased and after its been generated we're going to litter chest/traps and other gameplay elements on the map. However, theres no reason to put an item on a piece of that map thats not connected to the rest of the map.. Or worse yet, spawn a player on a tile thats unconnected to anything.

Does anyone know of a algorithm that helps with stuff like this?

Thanks in advance people.

~Etarnalazure

EDIT

What I'm looking for is an algorithm that makes sure theres no unconnected tiles, thus no items or players may by accident get seperated from the rest of the walk-able tiles.

Hopefully this clears up what i mean.

share|improve this question
what do you mean by 'connects properly'? Are there inaccessible terrain parts in your maps? – Timothy Groote Feb 6 at 10:37
4  
google "flood fill", it sounds like that might be useful for you – Jan Feb 6 at 10:38
Yeah, the problem is that currently I just randomly create holes in the map to simulate stuff like Lakes or just holes. But what if i end up creating holes a tile that a player starts on? Thats why i need a proper algorithm to make smart terrain. – Etarnalazure Feb 6 at 11:37
1  
Checking it out ASAP. – Etarnalazure Feb 8 at 8:19

3 Answers

up vote 3 down vote accepted

It sounds like you already have most of a terrain generator up and running. If your only concern is not leaving any walkable terrain isolated from other walkable terrain one thing you could do is run a blob finder over the entire map.

With one pass over the map grid you should be able to put together a collection of "blobs" which are separate walkable areas on your map. From there it should be fairly trivial to take each blob and make sure it connects with the rest by making a bridge/connection to one or more adjacent blobs and not stopping until there is only a single blob remaining (you can merge existing blobs without going over the entire map again).

If you need to spawn the player now, all you have to do is make sure that where you spawn them is walkable and you will be able to say for certain that they can get to any walkable square on the map.

share|improve this answer
Amazing mate! I will check it out. This answer is a lot more akin to what I was looking for :P – Etarnalazure Feb 9 at 17:11
up vote 3 down vote

Sounds like you're actually looking for a maze-generation algorithm instead of purely random terrain. Since most such algorithms work by "blazing a trail" from a starting point, there will be no islands.

share|improve this answer
up vote -1 down vote

If the core issue is really detecting if a bunch of stuff is connected, the way to address that would be with a pathfinding algorithm like A*.

I did a quick Google search and came up with this A* AS3 API.

share|improve this answer
Yeah, thats what we thought as well, we've made a rather in depth a* ourselves. We were just worried about memory usage if we had to run it to check for each tile. Had hoped there was a algorithm for smart terrain generation. Thanks regardless. – Etarnalazure Feb 6 at 14:43
4  
A* is for finding a path between two points. It's a bit overkill to check for a path between the player and every place where you want to place a chest. You'd more likely want something like a simple breadth first search, which doesn't need a end point to function properly. – Byte56 Feb 6 at 15:26
@Byte56 A* is fast-enough for most of the weird cases like this; given that you can get pre-canned implementations, that's usually "good enough." I've used it to detect connectivity of atoms for molecules in my Silverlight chemistry game, and it worked. Overkill? Maybe. Problem solved quickly? Aww yeah. – ashes999 Feb 6 at 20:59

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.