Help with an algorithm

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
yukino30
Posts: 13
Joined: January 27th, 2016, 9:36 am

Help with an algorithm

Post by yukino30 » August 16th, 2017, 9:25 am

Hello All,

I'm trying to make an algorithm for a minigame. I'm using chili framework to test the answer and then I'm planing to use the algorithm in Unreal4 (C++).

What I want is an algorithm which is able to get something similar to this:

https://i.stack.imgur.com/xm3u5.jpg

The blue cells are cells where a character can walk and the the black ones are "holes" or non-walkables cells.
As you can see in the picture the blue cells defined a path with not dead ends.
This is similar to a maze, and I know there are a bunch of good algorithms to generate mazes (I have a couple of them) but the algorithms that I found are mazes with walls, not exactly what I want.

At the moment I'm not able to generate a good solution, only some aproaches.

If anybody have an algorithm or any way to do this please let me know.

Thanks in advance

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Help with an algorithm

Post by albinopapa » August 16th, 2017, 2:32 pm

What exactly are you looking for?

The image almost looks like a Depth First Search generated maze.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
Manieknr1
Posts: 12
Joined: February 27th, 2017, 7:43 pm

Re: Help with an algorithm

Post by Manieknr1 » August 16th, 2017, 5:36 pm

I think you can use somthing like that:
1. get a starting position somwhere near a border of the grid by setting a CurrentPointer to this tile of the grid
2. roll a move direction
3. save your position in a pointer LastPos or something like that
3. move your CurrentPointer in direction you've rolled
4. make all of neigbours(if they exist and were not visited) of your lastPos unacessible, that means they are not posiible to become your move position, they are like walls
5.repeat


you should also have a stack of tiles you've visited so you can get back there if you are stuck
I've not written it in code it is just a concept, so I do not guarantee that this will work

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Help with an algorithm

Post by MrGodin » August 16th, 2017, 9:54 pm

Here is a maze generation solution which creates a txt file in the solution folder that is filled with 0's and 1's where 0 is a wall or impassable and 1 is good to go. You can then read the example.txt file into a program then generate a tile map or grid of rectangles and assign each grid cell to passable or not (0, or 1). Hope this helps. In the code you can change the width and height to the size you want, they just have to be odd numbers ie: width = 11, height = 21 ect
Edit:
Add this to put the width and height of the map in the first line in the text file

Code: Select all

if (myfile.good())
	{
		myfile << width << " " << height << endl; << new code
        .....
       }
Example Output to file

Code: Select all

21 21
000000000000000000000
011111110111011111110
000000010001010001000
011111010111010101110
010000010100010100010
011111010111010111010
010001010101010101010
010101010101010101010
010101010101010100010
011101110101111101110
000100000100000001010
010111110101111111010
010000010001000000010
010111010111011111110
010101010100000100000
010101110111110111110
010100000001010000010
010101111101010111010
010101000100010100010
011111011111110111110
000000000000000000000
Attachments
ConsoleApplication2.zip
(15.78 KiB) Downloaded 124 times
Curiosity killed the cat, satisfaction brought him back

yukino30
Posts: 13
Joined: January 27th, 2016, 9:36 am

Re: Help with an algorithm

Post by yukino30 » August 17th, 2017, 9:10 am

Thanks all for the answers.
MrGodin Thanks for the code!

Post Reply