The official site of Clan TMMM
 
HomeHomeSearchUsergroupsFAQRegisterLog in


Latest topics
» Gotta click fast - WC3 Mazing #mildlyinteresting
by hoffmann Wed Jun 21, 2017 10:28 pm

» Hey whats up
by Eat_bacon_daily Mon Oct 10, 2016 6:24 am

» I'm getting married and you guys are invited
by Achilles.42 Wed Sep 07, 2016 11:00 am

» Server Photo Album 1
by Pat1487 Sat Aug 06, 2016 5:28 pm

» Legacy of The Void Beta
by Achilles.42 Sun Oct 18, 2015 3:21 am

» Hey guys!!!
by Eat_bacon_daily Fri Oct 16, 2015 11:20 pm

» What everyone been up to
by The_Chosen_Oreo Sun Jun 14, 2015 11:55 am

SC2 Links
SC2 Challenge/Tourney Info

Official SC2 Forums

SC2 Curse

SC2Mapster

Team Liquid

SC2 Replayed

SC2 Strategy
WC3 Links
Clan_TMMM[Host] Info

WC3 Challenge/Tourny Rules

Epicwar
Poll
What game does everyone play now?
Starcraft 2
26%
 26% [ 8 ]
Warcraft 3
35%
 35% [ 11 ]
League of Legends
19%
 19% [ 6 ]
World of Warcraft
0%
 0% [ 0 ]
Diablo 2
0%
 0% [ 0 ]
No games at all
10%
 10% [ 3 ]
Other game not listed
10%
 10% [ 3 ]
Total Votes : 31
Transparency

Share | 
 

 Roguelike algorithm for maze generation?

View previous topic View next topic Go down 
AuthorMessage
Serenity09
Moderator
Moderator
avatar


PostSubject: Roguelike algorithm for maze generation?   Sat Nov 23, 2013 1:02 pm

EDIT: I was annoyed by how bad the code tags make the psuedocode look so I scrubbed the tags to match wc3c.net bc they have more clear highlighting
http://www.wc3c.net/showthread.php?p=1133926#post1133926



So the gameplay style for the project is one of a maze

maze gameplay:
 

concept:
 

psuedocode:
 

Question:
Here's where it finally get's interesting
How do you generate well fitted levels?
Summarized so far:
Each Maze Level is a large rectangular portion of the map
That rectangle is then filled with smaller rectangles (Maze Elements)
This is constrained by not only the rectangular size of the Maze Element but also the theme, entrances and exits, and relative inherent difficulty of the level vs how far into the game the player is
What then is a good setup for the algorithm to find this? And should it do other things, like generate several possibilities; rate them each via another algorithm; pick the best

So with this idea there would be a generator struct of which there was one static singleton that would take the dimensions that describe its relative size, the actual location of it within space, the theme and the difficulty range and from there would fit MazeElement rectangles into it procedurally linking elements starts and ends with a goal of filling the rectangle in a way that is *good*


Last edited by Serenity09 on Sat Nov 23, 2013 1:14 pm; edited 2 times in total (Reason for editing : forumclan has shitty syntax highlighting options)
Back to top Go down
Pat1487
Moderator
Moderator
avatar


PostSubject: Re: Roguelike algorithm for maze generation?   Sat Nov 23, 2013 2:29 pm

Serenity09 wrote:
The fun (and driving) factor for this idea is that the maze needs to be constructed in a somewhat random way.

At first I thought that having the full maze randomly generate itself as if cut from marble would be really cool but on reflection i think the algorithms to capture the arbitrary "fun-ness" of a maze would be waaaay complicated for the scope of this... and for me Smile

So I think what I've settled on as reasonably feasible is a set of predefined W x L-sized mazing elements and assigning each element descripters for mazing style, difficulty, length, physical size, start point, end point, physical makeup, onCreate, onPause, onResume methods, etc. with this model, the individual elements would be predetermined but their adjoining elements (and thus how the individual elements "play") will be semi-random.
Thats how i thought you were going to do it when you first mentioned it
I dont know how you would do it without having predefined areas, it wouldnt make a maze that made sense if it was completely random

Serenity09 wrote:
psuedocode:
 
This seems far more complex then it needs to be
It would be easier to build the maze sections in an area of the map that is hidden from view, and then have a function that copies that into the area you want it to be instead of manually typing out all the code for all the terrain for every section
That would take care of the orientation nightmare too since you could build each section in every orientation and then have the generation algorithm copy the section that is in the appropriate orientation

Serenity09 wrote:
How do you generate well fitted levels?
Theres 2 ways to do it
1. Make each section conform to a pattern so that the path(s) of each section can connect to the path(s) of any other section
The pattern can be diverse enough that people wouldnt recognize it as a pattern as long as you make enough sections
This would mean there would be dead ends though, i guess you could put gate switches on the dead ends or maybe continues or something that gives players a reason to do down those dead end paths

2. Categorize the sections into 3 categories, corners, edges, and middles and make it so that corner sections only ever get put on corners, edges on edges, and middles in the middle
There would be no dead ends, unless you put dead ends in a section, but there would be multiple paths in the middle to take rather then 1 like how mazes usually are

The first option is better imo
You need a start section and an end section too (or just a "checkpoint" section) for both of those that only gets generated at the beginning/end of a level
You also need a variable for how many sections the level has so that it can generate a maze that can actually be completed (and so that levels can be different sizes)



EDIT:
Pat1487 wrote:
That would take care of the orientation nightmare too since you could build each section in every orientation and then have the generation algorithm copy the section that is in the appropriate orientation
Actually now that i think about it the orientation wouldnt matter with either of the options i said since any orientation could connect to any other orientation
You would still need to build the different orientations, but the generation algorithm wouldnt need to care about the orientation, it would just need to know if theres a path that needs a connection point
Back to top Go down
Serenity09
Moderator
Moderator
avatar


PostSubject: Re: Roguelike algorithm for maze generation?   Sat Nov 23, 2013 3:15 pm

pat wrote:
This seems far more complex then it needs to be
It would be easier to build the maze sections in an area of the map that is hidden from view, and then have a function that copies that into the area you want it to be instead of manually typing out all the code for all the terrain for every section
That would take care of the orientation nightmare too since you could build each section in every orientation and then have the generation algorithm copy the section that is in the appropriate orientation
this would suck in that you wouldnt have to just rotate the terrain you would also have to redo the triggers, rects, units, etc etc etc.
i like that you could do each orientation different enough that it wouldnt have the work of coming up with a new element just the work of slightly altering how its played. but i was planning to use the "difficulty" parameter to accomplish something like this so this is a bit less of a selling point
what i was planning to do was implement all this framework stuff and then in that same map also write a output function to an external text file (surprisingly, totally possible) and then just rinse and repeat this for each element before importing them all into the final product.
i think doing a read / copy would cause too many lag spikes for a maze -- hopefully a paste of a stored array would be a lot better
what i think i would do is make a series of 2 dimensional arrays that represented the area of the element and then just have a helper function that rotated a 2 dimensional array however many 90 degree increments. all the main layout algorithm would need to know was the size of the maze element and where its default / rotated entrances / exits could be


pat wrote:
Theres 2 ways to do it
1. Make each section conform to a pattern so that the path(s) of each section can connect to the path(s) of any other section
The pattern can be diverse enough that people wouldnt recognize it as a pattern as long as you make enough sections
This would mean there would be dead ends though, i guess you could put gate switches on the dead ends or maybe continues or something that gives players a reason to do down those dead end paths
this only answers how to connect 1 element to the next, not how to pick elements to fill the area. as far as connecting elements go i like your idea of a pattern but im guessing ill need something more. maybe when an element is placed and is inserted into the pseudo list it will also call a link method that physically joins it to the previous element in the least distance possible (hopefully 1 tile or less)
your 2nd part answers that and goes well with the 1st part so maybe you intended them to be viewed as going hand-in-hand. but from what you said after i kinda doubt it

EDIT: on retrospect, there's also no reason for these structs to be abstract. Each of the predefined MazeElements can just be instances of the struct rather than extending it. Obviously there would be some bonuses to extending, but I don't think its worth the headache...?
Back to top Go down
Pat1487
Moderator
Moderator
avatar


PostSubject: Re: Roguelike algorithm for maze generation?   Sun Nov 24, 2013 11:41 am

Serenity09 wrote:
this would suck in that you wouldnt have to just rotate the terrain you would also have to redo the triggers, rects, units, etc etc etc.
You would only build the terrain, youd put the units and everything else in as part of the generation when it gets put in the place it generates to
Pre-building the terrain only saves some of the work, if you dont pre build the terrain then all of the work will be in the code which will take even longer

You can make it a bit easier by using a specific terrain type to mark out the places where a rect should go, when it sees that terrain type instead of copying it, it creates a rect in its place in the area of the maze that is generated
The rects it makes from that would be part of a rect array that you use to lay out units and patrols and w/e else you want in that section
You would need another variable that stores what section is being used so that the generator knows how to use the rect array to put everything in the correct place
All you would have to do is an if statement that checks the variable that stores the section and put what happens for each rect for each section by using the rect array for each case
Have the copy algorithm go from the top left to the bottom right and it should make rects in order from rect[0] to whatever the last rect is in that predictable order allowing you to know what rect will be where when it gets generated
Just make the rect array very large so that it cant get full and clear it once its done with a section

Serenity09 wrote:
i like that you could do each orientation different enough that it wouldnt have the work of coming up with a new element just the work of slightly altering how its played. but i was planning to use the "difficulty" parameter to accomplish something like this so this is a bit less of a selling point
I dont really know what you mean by difficulty parameter in this context
I assumed it meant that the maze would generate to be an appropriate difficulty, like the first maze it makes would use sections that you tag as being easy, and then it would start using harder sections as the players complete levels
I dont see how you can use that as a replacement for orientation, so you must mean something different by difficulty

Serenity09 wrote:
what i was planning to do was implement all this framework stuff and then in that same map also write a output function to an external text file (surprisingly, totally possible) and then just rinse and repeat this for each element before importing them all into the final product.
I dont know if wc3 can do it that way
The best way to do it would be to output the result of the read/copy to a text file, then use that as what builds it, that way the final map wouldnt need to read/copy since it has the result, but i dont think you can do it like that
Im not sure of the kinds of things that can be outputed though, so if you can output that, do that

Serenity09 wrote:
i think doing a read / copy would cause too many lag spikes for a maze -- hopefully a paste of a stored array would be a lot better
There might be lag when its generating a level, but during the level, when people are actually playing, it would be fine
It might take awhile to do, worst case scenario there would basically be a loading screen between each level, i dont know how long it would take though, but i dont think it would take too long

Serenity09 wrote:
what i think i would do is make a series of 2 dimensional arrays that represented the area of the element and then just have a helper function that rotated a 2 dimensional array however many 90 degree increments. all the main layout algorithm would need to know was the size of the maze element and where its default / rotated entrances / exits could be
Its the same as read/copy, helper is read (rotate) and main is copy (layout), would have about the same performance, might even be slower since your going to be rotating large arrays (the array for terrain would be incredibly large)
The main difference is that youd be typing a lot more code if you use this for terrain (also you could only have 10 possible terrain types with this, unless you use different terrain arrays for different sections which is just convoluted)

You could use it for the units and rects though, instead of what i was saying above, about using a special terrain type as a marker
Special terrain would be easier (and less code), but rotating multidimensional arrays is better

Serenity09 wrote:
this only answers how to connect 1 element to the next, not how to pick elements to fill the area. as far as connecting elements go i like your idea of a pattern but im guessing ill need something more. maybe when an element is placed and is inserted into the pseudo list it will also call a link method that physically joins it to the previous element in the least distance possible (hopefully 1 tile or less)
your 2nd part answers that and goes well with the 1st part so maybe you intended them to be viewed as going hand-in-hand. but from what you said after i kinda doubt it
It doesnt need to know how to pick elements to fill the area, all it needs to know is theres an element that needs to be connected
And it wouldnt need to connect something within 1 tile since each section is designed to connect to any other section, thats why you have orientations, so it will be able to connect things properly
It will fill the area on its own as it connects everything

Both options can do that
The first one doesnt care how sections are connected (which is why i like it better)
The second one connects things based on how that thing should be connected, like the top of a middle section might connect to the bottom of an edge, so all it cares about is connecting sections to the sections that its supposed to connect to
Back to top Go down
Serenity09
Moderator
Moderator
avatar


PostSubject: Re: Roguelike algorithm for maze generation?   Mon Nov 25, 2013 2:04 pm

pat wrote:
this would suck in that you wouldnt have to just rotate the terrain you would also have to redo the triggers, rects, units, etc etc etc.
You would only build the terrain, youd put the units and everything else in as part of the generation when it gets put in the place it generates to
Pre-building the terrain only saves some of the work, if you dont pre build the terrain then all of the work will be in the code which will take even longer
then you'd need an algorithm that rotated the unit's spawn location and patrol target with the orientation and if you're going to do that than there's no point to physically building the different terrain orientations unless

pat wrote:
You can make it a bit easier by using a specific terrain type to mark out the places where a rect should go, when it sees that terrain type instead of copying it, it creates a rect in its place in the area of the maze that is generated
The rects it makes from that would be part of a rect array that you use to lay out units and patrols and w/e else you want in that section
this almost would be good but its exactly why I don't use the GUI trigger builder anymore. good, pretty quick, dirty, tiny learning curve but you reach the ceiling very quickly and that would suck for a  project like this.

pat wrote:
You would need another variable that stores what section is being used so that the generator knows how to use the rect array to put everything in the correct place
All you would have to do is an if statement that checks the variable that stores the section and put what happens for each rect for each section by using the rect array for each case
what?

pat wrote:
Have the copy algorithm go from the top left to the bottom right and it should make rects in order from rect[0] to whatever the last rect is in that predictable order allowing you to know what rect will be where when it gets generated
Just make the rect array very large so that it cant get full and clear it once its done with a section
ive always wanted to know the exact dimensions of a terrain tile in wc3. i think its 128units, but i think i remember them being dicks and it being just slightly different

pat wrote:
Just make the rect array very large so that it cant get full and clear it once its done with a section
arrays are more like vectors in wc3
does wc3 have threading?

pat wrote:
ser wrote:
i like that you could do each orientation different enough that it wouldnt have the work of coming up with a new element just the work of slightly altering how its played. but i was planning to use the "difficulty" parameter to accomplish something like this so this is a bit less of a selling point
I dont really know what you mean by difficulty parameter in this context
I assumed it meant that the maze would generate to be an appropriate difficulty, like the first maze it makes would use sections that you tag as being easy, and then it would start using harder sections as the players complete levels
I dont see how you can use that as a replacement for orientation, so you must mean something different by difficulty
so i planned on having 2 different difficulties. the inherent difficulty of an area -- ie how difficult the terrain makes it -- and the wanted difficulty of a level. The "wanted difficulty" would be determined purely by which level the player is on. the inherent difficulty refers to how hard the terrain alone makes an element. a land maze without any other effects would have the lowest difficulty of 1 while a super fast reverse ice with momentum based movement might have something like a 10.
when an element was told to start or restart, it would ideally have a series of case statements that would be based on difficulty as to how the level is generated.
when i said that difficulty would offset the usefulness of having distinct orientations it was unrelated to using difficulty to help render orientation.

pat wrote:
I dont know if wc3 can do it that way
The best way to do it would be to output the result of the read/copy to a text file, then use that as what builds it, that way the final map wouldnt need to read/copy since it has the result, but i dont think you can do it like that
Im not sure of the kinds of things that can be outputed though, so if you can output that, do that
let's go back to this much later

pat wrote:

It doesnt need to know how to pick elements to fill the area, all it needs to know is theres an element that needs to be connected
And it wouldnt need to connect something within 1 tile since each section is designed to connect to any other section, thats why you have orientations, so it will be able to connect things properly
It will fill the area on its own as it connects everything
i don't like this because it constrains generation in a few ways.
lets consider your system -- let's say each "transition" point must fulfill a pattern and thus get's one of say three letters: X Y Z. the only patterns that will really work for this (that don't lose the point, simplicity, of doing it pattern based entirely) will have to use absolute measurements of where transitions are.  what this means is that the dimension of the side with the transition point will become a characteristic of the pattern rather than the element. Say the 'X' transition was to have the path end 3 units down the y-axis and 5 units up the y-axis, on the edge of the element. That means that all rectangles with a X transition will have two sides being 7 units. This would then make it slightly awkward to have 2 different transitions opposite eachother as you would have to have different patterns for the same size. On top of that, you would need a lot of different patterns to keep things interesting and then a lot of different actual implementations of that pattern and i dont have that kind of patience.

i want to come up with pseudo code for a few different algorithms before i pick, do you want to produce the pseudo code for this one?

this has gotten off topic a bit and that's my fault for how i set the initial thread description up

here's a picture which describes the situation


in this game each level will be a large rectangle -- in the picture above it is represented by the red rectangle. IGNORE THE GREEN BLOCKS, i've decided that I don't want them. pretend they're red

each element that composes the level will be a much smaller rectangle -- represented as the black rectangles

each element will have specific points on it where it "makes sense" that it can join other elements -- represented as blue squares in the black rectangles. this color is kinda a pseudo color: for all other intents and purposes it is black

which brings us back to the main point: help me think of an algorithm design that can arrange small maze element rectangles in the large red rectangle such that

  1. The first element of a level is a special checkpoint element. this can be placed wherever
  2. The last element of a level is a special endpoint element. you must reach this point to beat a level
  3. Each individual element must have at least one of its transition points next to a transition point from another element
  4. No rectangle overlaps another rectangle
  5. The resulting maze is not trivial. it can branch, pivot etc freely and randomly (it is not a straight line of connected elements)
  6. The last element of a level does not occur "too soon"
Back to top Go down
Pat1487
Moderator
Moderator
avatar


PostSubject: Re: Roguelike algorithm for maze generation?   Mon Nov 25, 2013 4:54 pm

Serenity09 wrote:
this almost would be good but its exactly why I don't use the GUI trigger builder anymore. good, pretty quick, dirty, tiny learning curve but you reach the ceiling very quickly and that would suck for a  project like this.
Its definitely quick and dirty but i dont see how it wouldnt be good enough, all the rects you want would be placed, then you use those rects to do everything else (like spawn units and set patrols)
You dont always have to do something the long and clean way

Serenity09 wrote:
pat wrote:
You would need another variable that stores what section is being used so that the generator knows how to use the rect array to put everything in the correct place
All you would have to do is an if statement that checks the variable that stores the section and put what happens for each rect for each section by using the rect array for each case
what?
I was explaining what you said would be a problem here:
Serenity09 wrote:
then you'd need an algorithm that rotated the unit's spawn location and patrol target with the orientation and if you're going to do that than there's no point to physically building the different terrain orientations unless
You wouldnt need to rotate the spawn locations or patrols because youd be typing out the code for each orientation as if it was its own section rather then trying to rotate everything for that section

Serenity09 wrote:
does wc3 have threading?
I dont know, probably not

Serenity09 wrote:
i don't like this because it constrains generation in a few ways.
lets consider your system -- let's say each "transition" point must fulfill a pattern and thus get's one of say three letters: X Y Z. the only patterns that will really work for this (that don't lose the point, simplicity, of doing it pattern based entirely) will have to use absolute measurements of where transitions are.  what this means is that the dimension of the side with the transition point will become a characteristic of the pattern rather than the element. Say the 'X' transition was to have the path end 3 units down the y-axis and 5 units up the y-axis, on the edge of the element. That means that all rectangles with a X transition will have two sides being 7 units. This would then make it slightly awkward to have 2 different transitions opposite eachother as you would have to have different patterns for the same size. On top of that, you would need a lot of different patterns to keep things interesting and then a lot of different actual implementations of that pattern and i dont have that kind of patience.

i want to come up with pseudo code for a few different algorithms before i pick, do you want to produce the pseudo code for this one?

this has gotten off topic a bit and that's my fault for how i set the initial thread description up

here's a picture which describes the situation


in this game each level will be a large rectangle -- in the picture above it is represented by the red rectangle. IGNORE THE GREEN BLOCKS, i've decided that I don't want them. pretend they're red

each element that composes the level will be a much smaller rectangle -- represented as the black rectangles

each element will have specific points on it where it "makes sense" that it can join other elements -- represented as blue squares in the black rectangles. this color is kinda a pseudo color: for all other intents and purposes it is black

which brings us back to the main point: help me think of an algorithm design that can arrange small maze element rectangles in the large red rectangle such that

  1. The first element of a level is a special checkpoint element. this can be placed wherever
  2. The last element of a level is a special endpoint element. you must reach this point to beat a level
  3. Each individual element must have at least one of its transition points next to a transition point from another element
  4. No rectangle overlaps another rectangle
  5. The resulting maze is not trivial. it can branch, pivot etc freely and randomly (it is not a straight line of connected elements)
  6. The last element of a level does not occur "too soon"
I think your misunderstanding what my system is
Its the same sort of system diablo (and other games) uses for randomly creating dungeons, theres pre built rooms that all fit together in any way and they are linked together directly

Like this image:

Those are all the possible rooms for 1 of the dungeons in 1 of the acts in diablo 3
They can all connect to each other because the entrances are the same size and the game randomizes how they connect together by checking if theres a valid connection point up until a limit is reached (idk what they use for the limit, maybe once theres a certain number of rooms it generates the exit)
Basically what i was saying was to have the paths be in the same places on 1 or more of the sides of the sections (since mazes use paths instead of rooms) so that they all line up and can connect, and essentially mimic that system
There would be no recognizable pattern to it since it would appear to be a normal path, the only pattern people would recognize is that there are sections being repeated (which is fine if you have a lot of sections so that they dont repeat too often)

And i dont really understand your image, how does that translate into maze paths, the 3rd one on the top is especially confusing because it can connect to anything even though there might not be a path there, unless you have a path going in a square around the whole edge
If you were making rooms it makes sense (although the last 3 on the top have difficulty connecting to each other in certain configurations), but i cant make sense of it as a maze path
Back to top Go down
 
Roguelike algorithm for maze generation?
View previous topic View next topic Back to top 
Page 1 of 1
 Similar topics
-
» Voxel terrain generation
» Second/Third Generation Death Knights
» Book Review: 39 Clues, Maze of Bones
» Generation 8 of Consoles
» The Kooky Spooky Maze

Permissions in this forum:You cannot reply to topics in this forum
Clan TMMM :: Warcraft 3 :: WC3 Tutorials and Help-
Jump to: