Poll | | What game does everyone play now? | Starcraft 2 | | 26% | [ 8 ] | Warcraft 3 | | 35% | [ 11 ] | League of Legends | | 19% | [ 6 ] | World of Warcraft | | 0% | [ 0 ] | Diablo 2 | | 0% | [ 0 ] | No games at all | | 10% | [ 3 ] | Other game not listed | | 10% | [ 3 ] |
| Total Votes : 31 |
|
|
| Roguelike algorithm for maze generation? | |
| | Author | Message |
---|
Serenity09 Moderator
| Subject: 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#post1133926So the gameplay style for the project is one of a maze - maze gameplay:
There is a path - dictated by terrain type - of any size and arrangement leading from the "start" to the "finish". Each player gets a single unit and must navigate that unit from start to finish keeping on the path. Your unit dies when it strays from the path. There are also other obstacles to the maze that kill your mazing unit on collision. These range most usually include non-moving, patrolling or wisp wheel obstacles, but anything fitting is fair game. When dead you must wait for a revive condition before trying again (some revive conditions are that your full team has died but has a extra life, some are immediate revival so long as you have a life left.
- concept:
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 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.
- psuedocode:
I would love to hear encapsulation critiques or logic suggestions, but please bear with the haphazard pseudocode -- its been awhile The basic idea is that there are a bunch of MazeElements inside of a LevelElement. This section doesn't actually worry at all about how they're picked only about representing the Generated Maze after it's been generated. - Code:
-
public abstract struct LevelElement MazeElement[] mazeElements int levelTheme Point actualTopLeft Point actualBotRight LevelElement levelBefore LevelElement levelAfter
public method width takes nothing returns double return // endmethod public method length takes nothing returns double return // endmethod
public static method create takes /*the above*/ returns LevelElement local LevelElement le = LevelElement.allocate() /*map to le*/ return le endmethod endstruct
- Code:
-
public abstract struct MazeElement /* I know that there aren't two-dimensional arrays for vJASS but I don't want to relearn the syntax for hashmaps just yet */ int[][] terrainTemplate Point topLeft /*describes size of Element*/ Point botRight Point actualTopLeft /*describes position of Element in Game Grid*/ Point actualBotRight int orientation /*this one is going to be hard... 1: 0 clockwise, 2: 90 clockwise, 3: 180: clockwise 4: 270 clockwise*/ rect Area code onCreate code onPause code onUnpause int themeID double difficulty Point[] elementEntrances /*I'm sure it leaks, just pseudocode*/ Point[] elementExits LevelElement levelContainer /*If I can't have a two directional reference between structs, this will just be a levelContainerID and LevelElement will have a static accessor based on ID*/ MazeElement elementBefore MazeElement elementAfter
/*a bunch of other descriptive attributes more related to in-game accumulated data*/ public stub method onPause takes noting returns nothing call Execute(this.onPause) endmethod
public stub method onUnpause takes noting returns nothing call Execute(this.onUnpause) endmethod static method create takes int[][] terrainTemplate, Point topLeft, Point botRight, Point actualTopLeft, Point actualBotRight, int orientation, code onCreate, code onPause, code onUnpause, int theme, double difficulty, Point[] elementEntrances, Point[] elementExits, LevelElement levelContainer, MazeElement elementBefore, MazeElement elementAfter /* , &rest */ returns MazeElement local MazeElement me = MazeElement.allocate() /*map variables*/ set me.Area = new rect(topLeft, botRight).centerOn((actualBotRight.x + actualTopLeft.x) / 2, (actualTopLeft.y + actualBotRight.y) / 2) /*total guess at syntax*/ call setTerrainHelper(int[][] terrainTemplate, Point actualTopLeft, Point actualBotRight, int orientation) /*not touchin' this rat's nest for now*/ call Execute(onCreate) endmethod endstruct
The predefined set of MazeElements would effectively be a list of objects that contain the relevant info plugged in by me. I would probably modify the above code to make it more reusable for this purpose. If anyone has a suggestion for the logicflow to do this I would be interested, I have always just winged it when it comes to a schematic representation meant for reproduction via a factory-type-thing
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) | |
| | | Pat1487 Moderator
| Subject: 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
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:
I would love to hear encapsulation critiques or logic suggestions, but please bear with the haphazard pseudocode -- its been awhile The basic idea is that there are a bunch of MazeElements inside of a LevelElement. This section doesn't actually worry at all about how they're picked only about representing the Generated Maze after it's been generated. - Code:
-
public abstract struct LevelElement MazeElement[] mazeElements int levelTheme Point actualTopLeft Point actualBotRight LevelElement levelBefore LevelElement levelAfter
public method width takes nothing returns double return // endmethod public method length takes nothing returns double return // endmethod
public static method create takes /*the above*/ returns LevelElement local LevelElement le = LevelElement.allocate() /*map to le*/ return le endmethod endstruct
- Code:
-
public abstract struct MazeElement /* I know that there aren't two-dimensional arrays for vJASS but I don't want to relearn the syntax for hashmaps just yet */ int[][] terrainTemplate Point topLeft /*describes size of Element*/ Point botRight Point actualTopLeft /*describes position of Element in Game Grid*/ Point actualBotRight int orientation /*this one is going to be hard... 1: 0 clockwise, 2: 90 clockwise, 3: 180: clockwise 4: 270 clockwise*/ rect Area code onCreate code onPause code onUnpause int themeID double difficulty Point[] elementEntrances /*I'm sure it leaks, just pseudocode*/ Point[] elementExits LevelElement levelContainer /*If I can't have a two directional reference between structs, this will just be a levelContainerID and LevelElement will have a static accessor based on ID*/ MazeElement elementBefore MazeElement elementAfter
/*a bunch of other descriptive attributes more related to in-game accumulated data*/ public stub method onPause takes noting returns nothing call Execute(this.onPause) endmethod
public stub method onUnpause takes noting returns nothing call Execute(this.onUnpause) endmethod static method create takes int[][] terrainTemplate, Point topLeft, Point botRight, Point actualTopLeft, Point actualBotRight, int orientation, code onCreate, code onPause, code onUnpause, int theme, double difficulty, Point[] elementEntrances, Point[] elementExits, LevelElement levelContainer, MazeElement elementBefore, MazeElement elementAfter /* , &rest */ returns MazeElement local MazeElement me = MazeElement.allocate() /*map variables*/ set me.Area = new rect(topLeft, botRight).centerOn((actualBotRight.x + actualTopLeft.x) / 2, (actualTopLeft.y + actualBotRight.y) / 2) /*total guess at syntax*/ call setTerrainHelper(int[][] terrainTemplate, Point actualTopLeft, Point actualBotRight, int orientation) /*not touchin' this rat's nest for now*/ call Execute(onCreate) endmethod endstruct
The predefined set of MazeElements would effectively be a list of objects that contain the relevant info plugged in by me. I would probably modify the above code to make it more reusable for this purpose. If anyone has a suggestion for the logicflow to do this I would be interested, I have always just winged it when it comes to a schematic representation meant for reproduction via a factory-type-thing
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 | |
| | | Serenity09 Moderator
| Subject: 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...? | |
| | | Pat1487 Moderator
| Subject: 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 | |
| | | Serenity09 Moderator
| Subject: 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
- The first element of a level is a special checkpoint element. this can be placed wherever
- The last element of a level is a special endpoint element. you must reach this point to beat a level
- Each individual element must have at least one of its transition points next to a transition point from another element
- No rectangle overlaps another rectangle
- The resulting maze is not trivial. it can branch, pivot etc freely and randomly (it is not a straight line of connected elements)
- The last element of a level does not occur "too soon"
| |
| | | Pat1487 Moderator
| Subject: 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
- The first element of a level is a special checkpoint element. this can be placed wherever
- The last element of a level is a special endpoint element. you must reach this point to beat a level
- Each individual element must have at least one of its transition points next to a transition point from another element
- No rectangle overlaps another rectangle
- The resulting maze is not trivial. it can branch, pivot etc freely and randomly (it is not a straight line of connected elements)
- 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 | |
| | | Sponsored content
| Subject: Re: Roguelike algorithm for maze generation? | |
| |
| | | | Roguelike algorithm for maze generation? | |
|
Similar topics | |
|
| Permissions in this forum: | You cannot reply to topics in this forum
| |
| |
| |