Random tiling with a path?

So here is a problem I'm not entirely sure how to approach. I need to randomly tile my game grid, but also guarantee there is a path.

Basically I need to prevent this:

<img src="http://i.imgur.com/swnxZ0Y.png" border="0">

You'll notice there is no way to start at the left and make it to the right because of walls.

Here is the capx: BoardGame.capx

Can anyone help me?

Here are two approaches you could try:

a) you could use more sophisticated generation algorithm (google) that would make sure that such path happens.

b) you could generate your walls randomly, and use something like pathfinding behavior to find out if there is path between two points. If not, you could regenerate whole map, or remove (randomly or semi-randomly) a wall. Repeat the process until path is found.

I've decided to go with the pathfinding approach since a lot of the algorithms I've found online are going over my head in terms of implementation.

However, there seem to be some missing conditions - in particular, 'On path found' and 'Failed to find path'

<img src="http://i.imgur.com/CHYf2nu.png" border="0" />

Does anyone know where these went?

The missing conditions are triggers and there can only be one trigger per event. So you'll only see them in events that aren't sub-events of a trigger and don't have a trigger in them already.

Alright, so I've tried to implement this using the pathfinding behavior, but I'm having issues. For debugging purposes, I have disabled the destroying of the two 'path check' sprites. So the problem now is, these two sprites aren't showing up at all. Can someone take a look?

<img src="http://i.imgur.com/3UbpAAq.png" border="0">

Here's the .capx: BoardGame.capx

.CAPX file is updated. Here's what it looks like. Still not working.

<img src="http://i.imgur.com/njoh9im.png" border="0" />

I am pretty sure there have been a couple of capx with sample map generators that solve this already on the forums, sorry I can't take the time to find them right now as I have to go, but I know there are a couple. Look for cave generator or map generator and you should find something here in the forums.

interesting problem

here's my solution

randomPath.capx

The algo in a nutshell:

maze algorithm -> deduce a path -> remove the maze and create something more random while preserving the path

Interesting. I've tried to avoid maze algorithms because they tend to always produce only one path, whereas I would want it more random and sometimes have several paths. That's why I've resorted to the random tiling approach that I have.

Sometimes I get several paths using your method, other times I get only one. I suppose as far as random tiling goes, there is no way to guarantee two distinct paths. Your solution will probably do for now. Thanks, —

I made a labrynth generator, but it is slow.

Somewhere in the net I saw this nice approach:

-make random "rooms" appear in the map.

-Then connect rooms with paths.

Giving a number to each room, shuffling it and making paths to connect all rooms should be easy.

That's the place where I found this idea:

gamestorm.tumblr.com/post/26710904435/this-is-a-simple-labyrinth-small-code-mechanic

Excal

Maybe you can run the maze algo more than once to create 2 or 3 different path before generating the entire map the way I did it.

Yann, so many globals in the example that it bothers me :P

When the maze function is called, the maze array is cleared and then the vector array is created. Would I need to clear this vector array if I intend to run the maze function multiple times? There is no 'clear direction array' in the vector function. Would I need to create a second vector list?

Excal

Four of the globals are semantic constant use every where. (well the EMPTY and WALL are just used for the Maze Generation part so you could put them in local constant in this group if you really want)

There shouldn't be any issue with them, and I found out that they were more helpfull in global scope than in local. If you were to define the same constant at other places you wouldn't be sure of if they have the same value or not. I think local constant can lead to confusion.

Now the 3 other constant (WIDTH,HEIGHT and DENSITY) are parameters for the whole algorithm. Soooo I think they have their place on global scope as well.

As far as the runtime variable, generating is a kind of global state of the algorithm so well.. makes sense to be global, and for the three last, if I could initialize them with an expression as it's possible in C they would also be constant.

So yeah as much as I would agree with you that too much globals is bad because of global namespace cluttering and overall incertainty (which doesn't exist with constant). I think these ones are justified.

Now as far as the vector list is concerned, you could actually put the function on start of layout.

The vector list is just a look-up table of the four possible directions you can travel in the maze.

It looks like:

Array.At(0,0) =  1
Array.At(0,1) =  0
Array.At(1,0) =  0
Array.At(1,1) =  1
Array.At(2,0) = -1
Array.At(2,1) =  0
Array.At(3,0) =  0
Array.At(3,1) = -1

Yann

This makes more sense, thanks!

I've tried to edit your .capx to account for the cellsize I wanted (64x64), but now it seems broken. I also removed the mouse-clicking for spawning the Start and End, and instead just had them placed automatically.

Can you take a look?

BoardGame.capx

Excal

You have a mix of face palm error, object/project settings error and some arithmetical errors

The face palm error is the fact that the GridTiles layer isn't transparent.

So you don't see what is created on Layer 0.

The object settings error is that you don't have the same Cell Size value in your finder in your ObjectDump and in your Gameplay Layouts. It does not necessarily cause the bug, but well... better safe than sorry (:

The project setting error is that you have a layout width which is not a multiple of 64, so it doesn't look good

The arithmetical ones are where you position your end point, and is a bit bound to the layout width error and some wrong calculation

You try to place the end sprite at floor(WIDTH/cellSize)*cellSize which in fact put it out of the layout. The proper formula would be (floor(WIDTH/cellSize)-1)*cellSize

Also since the origin is at the center of the sprite, you have to offset it to half cellSize.

So the proper formula would be:

X = (floor(WIDTH/cellSize) - 0.5) * cellSize

Y = (floor(WIDTH/cellSize) - 0.5) * cellSize

Oh and also I think you were generating the maze constantly... soooo

Excal-RandomPath.capx