![]() |
#1 | |||
User
Join Date: Jul 2010
Posts: 76
![]() |
![]() So the gameplay style for the project is one of a maze
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 Yrth : 11-24-2013 at 12:42 AM. |
|||
![]() |
![]() |
Sponsored Links - Login to hide this ad! |
|
![]() |
#2 |
Procrastination Incarnate
Development Director
|
![]() In general, this is a very complex problem, but the specifics of your map might make it doable.
__________________While this genre of the map is called a "maze", I assume you don't really want it to be a maze, that is, a heavily branching path with a lot of dead ends. Rather, you want it to be an obstacle course, a linear path assembled out of random obstacles. The goal is to have a randomly assembled winding path that fills up the available space as much as possible. In this case, the task can be broken down somewhat: you can first lay out the course of the path on a grid, then fit maze elements on top of this path. This can still be a pretty complicated algorithm. The simplest solution I can think of would be to check every possible element (or at least every element with an appropriate difficulty/theme) whether its layout matches the layout of the path from the current position onward; once a list of elements that can fit is assembled, an element is chosen at random, with possible probability modifiers that make more suitable elements more likely (such as the ones with the best difficulty fit, ones that haven't been used before, longer ones, or ones that fit better with the previous element). Even with probability modifiers, this approach would likely mostly ignore larger maze elements because they are much less likely to fit the path than a simple 1x1 element. A 1x1 element only moves the current position forward by 1 grid space so that's not by itself a problem but a 2x1 element moves forward by 2 spaces which can cause an algorithm to miss one of the rare spaces where a larger 3x2 element could have fitted. One possible improvement of such an algorithm would therefore be, when inserting a medium-sized maze element, to check if any of the covered path positions could instead fit a larger element and if so, use a shorter element. Another possible way to increase the likelihood of a larger element being used would be to not require a perfect fit. As long as the path enters an exits the element's area at the right points, it doesn't matter how it winds through the area of the element (the only possible problem you'd need to check for would be if the path leaves some parts of the element uncovered and then later strays into that area again). It's always safe to shorten the path, so even if it strays out of the area of the element being considered, that element can still be used if the path later returns to the area and exits it at the element's exit point. You can also increase the likelihood of larger elements being used by making more of them, like multiple variations of the same element with different exit points. In practice, you are probably unlikely to make elements larger than 3*3 or 4*2, most will probably be x*1. |
![]() |
![]() |
![]() |
#3 | |||
User
Join Date: Jul 2010
Posts: 76
![]() |
![]() Thanks for such a thorough reply, Anitarf.
Quote:
it is linear only in that there exists a path from the start to the end. i would much rather not constrain it to being necessarily a single path -- the data structure that resembles a level most is much more a Graph with sets of nodes and edges instead of a list with a set of one-in, one-out nodes. but this is not so much a requirement as a "wouldn't it be awesome if..." Quote:
Quote:
let me elaborate a bit ![]() in this game each level will be a large rectangle -- in the picture above it is represented by the red rectangle. if anitarf's idea for an initial path composed of 1x1 squares ends up being the best way forward, than the green squares in the rectangle will represent that start and the finish. otherwise, pretend they're red each element that composes the level will be a much smaller rectangle -- represented as the black rectangles, in the actual game there will be many more of these and with more varied sizes 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. for now, because it is simpler to do so, all transition points are equal. in the actual code though, this will be further defined by whether or not the point is an exit, entrance, or both. all transition points, for now, can be assumed to be both for simplicities sake. 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
in my experience, only a few mazing elements need to have a 1x1 entrance and exit that can occur in one spot only. it is probably this part that makes me like your initial random path generation algorithm idea so much |
|||
![]() |
![]() |
![]() |
#4 |
Procrastination Incarnate
Development Director
|
![]() The reason I assumed a non-branching path is because that's what most maze maps are like, they are not really mazes but obstacle courses. Making this assumption also simplifies the problem somewhat. I'm not really sure how I'd approach an actual problem of assembling a real maze... it seems like a kind of problem that should have a lot of literature already written about it, though, so maybe you could find and study that. If you don't feel like going all academic on the problem then I suggest you simplify it.
__________________One possible simplification is working with a larger grid and/or smaller elements. In your example graphic, most of the elements are way bigger than I imagined them, the solution I described wouldn't work with them at all since the odds of getting any of the larger elements to in any way match the path would be practically zero. Like I said, I was thinking about elements up to 3x3 in size. (obviously, the biggest simplification you could make would be to make all elements 1 grid space big; however, I don't think we need to make the problem that simple in order to solve it) It's also always possible to substitute clever algorithms with brute force; just randomly assemble stuff until you get something that meets some criteria; the problem here is that, if your success rate is low enough, you run the risk of randomly getting an absurd load time as the dumb algorithm may end up having to crunch through thousands of mazes to get one that works. Even then, there's not much guarantee that it works well. That's another thing to consider: is the end result actually what you want from the gameplay perspective? Wouldn't it be frustrating for the players to dodge a difficult wisp wheel only to discover the path they were following was a dead end? I can understand the appeal of making it an actual maze, though, because it benefits the most from having randomly assembled levels. Still, even with that synergy, would a maze actually be more fun to play than an obstacle course? |
![]() |
![]() |
![]() |
#5 | ||||
User
Join Date: Jul 2010
Posts: 76
![]() |
![]() Quote:
do you still play / program for wc3 at all? Quote:
Quote:
do you have any idea of in game limits and where i will be pushing these things? say i'm feeling truly motivated in this project and come up with 40 distinct elements. each of those elements will have on average an int[5][5] array (or equivalent of some sort) describing their terrain as well as will store triggers / rects describing their in game behaviour. every such "template" element will have its contents just hanging out occupying memory for the length of the game unless i want to do alllll generation at game start i can avoid duplication of the "what does its terrain look like" array but everything else will have to have a local copy because any static alternative seems truly awful. but also, it will be a huge limitation to generation to have only the default orientation of each element possible, so instead each element will need to be re-oriented for all 90degree possibilities. making this 4x that in overhead that is just from templates though, each level will have to make actual instances of those element templates and keep them in memory. potentially i can delete them as they come and go, but this is a fall back sidenotes: I remember that all objects (or are they called handles?) leak unless you specifically set them to null. are wc3 arrays an object? The event for "when a unit enters a rect" -- does that actually just have a full list of all rects with this event attached to them and then periodically check to see what units are newly inside of them? does wc3 have multiple threads? how are all clients kept to the same thread(s) (the host im guessing)? Is there anyway to directly access the data structure representing the terrain of a map? (this is a big one) say i define a struct that will serve as a template for maze elements and it has as a member variable some code. this code will be run whenever a player is within that element, how that happens doesn't matter. when i create a new instance of that struct will it duplicate the code variable as i would expect or instead provide a reference to the original? Quote:
so far they have included: long empty paths between elements -- plan to prevent: have each element be directly adjacent to at least one other element and work this into the code. as a fall back for scenarios where this isn't possible: include a small set of linking elements that are x by 1 to get out of fragmented zones no power to do anything non-trivial dynamically -- plan to prevent: have each element include pseudo lambda functions defining the elements behavior when its first created, what should happen when its on, what should happen when its off weird generations -- plan to prevent: beg people for help until solved |
||||
![]() |
![]() |
![]() |
#6 |
www.raodaozao.net
MDL & Resource Moderator
|
![]() I'm not sure how relevant this might be to you, but I relatively recently implemented a maze generator in WC3.
__________________I used the growing tree algorithm: http://pcg.wikidot.com/pcg-algorithm:maze The gist of it is that you take a start point and then walk away from it, choosing the next block to go to based on some criteria. This way, the maze is guaranteed to be traversable, and all you need to do is pick a sufficiently far-away block that has walls on all sides as the "exit". Means you don't have to worry about randomness making the maze uncompletable, and you can weight the algorithm to produce less branches so you can focus on the one long winding route with only a few diversions. It's a bit odd to get your head around, but I followed the Python code example in that link and it worked out all right for me. |
![]() |
![]() |
![]() |
#7 | |||||
Procrastination Incarnate
Development Director
|
![]() Quote:
Quote:
Quote:
Quote:
Quote:
|
|||||
![]() |
![]() |
![]() |
#8 | ||||||
User
Join Date: Jul 2010
Posts: 76
![]() |
![]() Quote:
I love that algorithm, its my favorite of the common maze generators! that's even the same page I learned from lol you might enjoy this (very good) slide show on maze generators that i found. the different heuristic demonstration is cool growing tree Unfortunately a lot of the reason it works so well is that it makes the assumption that each tile that it places is the same size, and thus can be simplified to being a 1x1 square. All bets are off when what youre actually dealing with comes in different flavors. I've thought a lot about whether or not I could follow the same general algorithm as a 1x1 maze generator and I still haven't decided really. Since each "tile" would be a rectangle of different size, choosing a neighbor may be rather rough. on top of that, even though it is designed to be fully connected and reach from start to exit, in order to effectively create a main branch you would need to define a heuristic that effectively picks a next neighbor based on close-ness to exit most of the time. But than that will (of course) generate plenty of random "bugs" so instead you would have to give each possible tile a flag for whether or not its part of the main branch. but at that point, the algorithm is no longer "The Growing Tree" but is now "The Frankenstein Growing Tree" Quote:
atomics: don't leak objects: leak unless properly nulled arrays of atomics: ? Quote:
Quote:
Quote:
ooph that's a pretty big blow to my motivation, I don't really know if I want to get into using interfaces in my case how would this work? Each MazeElement needs to have 3 different functions that it can call that are bound to that particular instance. So MazeElement e = ... e.Start() e.Pause() e.Unpause() there will be 10 other MazeElement instances that all need to do the above However the actual contents of Start, Pause, Unpause will be different from example to example. I never really picked up interfaces, which i know i really should, so this is going to be pretty sketchy but ![]() interface IMazeElement function Start() function Pause() function Unpause() endinterface struct MazeElement implements IMazeElement static method create (code s, code p, code u) me.Start = s me.Pause = p me.Unpause = u endmethod endstruct or alternatively, can you place code into a global hashmap [primary key being the maze element, secondary key being 0:start, 1:pause, 2:unpause] and get / run it from that? |
||||||
![]() |
![]() |
![]() |
#9 | ||||
default string
|
![]() Quote:
Quote:
Quote:
Quote:
![]() function interface MazeCallback takes nothing returns nothing struct MazeElement MazeCallback Start MazeCallback Pause MazeCallback Unpause static method create takes MazeCallback s, MazeCallback p, MazeCallback u returns MazeElement local MazeElement this = MazeElement.allocate() set .Start = s set .Pause = p set .Unpause = u call .Start.execute() return this endmethod endstruct ... function SomeMazeCallbackFunction takes nothing returns nothing //Do your stuff in here endfunction ... MazeElement e = MazeElement.create(SomeMazeCallbackFunction, SomeMazeCallbackFunction, SomeMazeCallbackFunction) You could also use interfaces but then you'd need a different struct for each Maze. You can check them out in the readme too if you want. Last edited by Fledermaus : 11-27-2013 at 09:33 PM. |
||||
![]() |
![]() |
![]() |
#10 | |
User
Join Date: Jul 2010
Posts: 76
![]() |
![]() Hi Fledermaus, thank you for the reply!
Quote:
ohhhh I didn't even realize function interfaces were a thing. they seem much more relevant than normal interfaces here... whoa that's so weird, the interface pulls all functions with matching signatures (including parameter names) into it as static member variables either way, using this makes much more sense... in my example I had no idea how I would be able to reference the specific MazeElement object but with a function interface thats like ![]() function interface FIMazeElement takes MazeElement me returns nothing function MazeElementOneStart takes MazeElement me returns nothing //... endfunction but then when i go to create a new instance of the struct and try to pass in ![]() MazeElementOneStart ![]() FIMazeElement.MazeElementOneStart i guess my new question is: from an OOP POV, what is better?
|
|
![]() |
![]() |
![]() |
#11 |
default string
|
![]() I'd personally just use function interfaces as I find them easier. Either will work and they both have their downsides:
- More structs created with struct interface way - More function interfaces created with function interface way (they're actually run via creating a trigger per function and running that) Last edited by Fledermaus : 11-27-2013 at 11:53 PM. |
![]() |
![]() |
![]() |
#12 |
Procrastination Incarnate
Development Director
|
![]() It doesn't really matter whether you extend an interface (or a struct with stub methods) or whether you use function interfaces. I suppose the function interface way is a bit more dynamic since all your elements are the same type so you can more easily create and copy them, as opposed to them each being a separate static type that extends the main interface. Since you need to be able to dynamically allocate new instances of the elements as you build the maze, the function interface solution is probably better, although regular interfaces also allow you to create any of its subtypes provided all the subtype create methods take the same parameters. you could also make the actual instances of the elements in the maze a separate struct that then references the interface.
__________________In short, the approaches are pretty much interchangeable so which one you use usually depends mostly on your coding style. |
![]() |
![]() |
![]() |
Thread Tools | Search this Thread |
|
|