Random tiling with a path?

Get help using Construct 2

Post » Fri Apr 19, 2013 2:31 pm

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:



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?
Project Lead of Zems Online Card Game

Producer at Impulse Limited
B
18
S
6
G
3
Posts: 677
Reputation: 5,194

Post » Fri Apr 19, 2013 2:40 pm

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.
B
24
S
8
G
7
Posts: 756
Reputation: 7,192

Post » Fri Apr 19, 2013 3:00 pm

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'



Does anyone know where these went?
Project Lead of Zems Online Card Game

Producer at Impulse Limited
B
18
S
6
G
3
Posts: 677
Reputation: 5,194

Post » Fri Apr 19, 2013 7:02 pm

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.
B
79
S
24
G
53
Posts: 4,728
Reputation: 40,219

Post » Sat Apr 20, 2013 1:14 pm

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?



Here's the .capx: BoardGame.capxExcal2013-04-20 13:15:18
Project Lead of Zems Online Card Game

Producer at Impulse Limited
B
18
S
6
G
3
Posts: 677
Reputation: 5,194

Post » Mon Apr 22, 2013 6:05 am

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

Project Lead of Zems Online Card Game

Producer at Impulse Limited
B
18
S
6
G
3
Posts: 677
Reputation: 5,194

Post » Mon Apr 22, 2013 7:39 am

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.
B
49
S
11
G
10
Posts: 1,833
Reputation: 14,418

Post » Mon Apr 22, 2013 4:44 pm

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
Last edited by Yann on Sun Sep 14, 2014 7:19 pm, edited 1 time in total.
B
60
S
22
G
14
Posts: 1,479
Reputation: 16,346

Post » Mon Apr 22, 2013 9:44 pm

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, @Yann.
Project Lead of Zems Online Card Game

Producer at Impulse Limited
B
18
S
6
G
3
Posts: 677
Reputation: 5,194

Post » Mon Apr 22, 2013 11:02 pm

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:
http://gamestorm.tumblr.com/post/26710904435/this-is-a-simple-labyrinth-small-code-mechanic
B
39
S
11
G
5
Posts: 132
Reputation: 8,228

Next

Return to How do I....?

Who is online

Users browsing this forum: No registered users and 31 guests