Algorithm ideas for a roguelike effect on a maze?

[Yrth]

So 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. JASS: 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 JASS: 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 EDIT: on retrospect, there's 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...?

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*

[Anitarf]

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.

[Yrth]

Thanks for such a thorough reply, Anitarf.

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

that's correct with a few changes
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..."

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.

i didn't think of it all like this but i like the idea. obviously for it to work in an maze environment it would need a minimum length between turns, but that's totally doable. can you think of any other cons besides the natural bias towards small elements? as i said above, i think a graph representation would be cool as it would give the game a adventure-game type feel. by effectively laying out the "main" branch of the graph we limit the space that the smaller off shoot branches can occupy to potentially trivial and un-fillable dimensions (hard drive fragmentation makes a good parallel to this). do you have any ideas on how to keep the main branch as interesting as possible while attempting to eliminate pointlessly-trivial side branches (this isn't the main concern but would be a very cool bonus)

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.

hmm do you think that it would really present that much of a problem or is this maybe my fault for not being clear enough
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

1. The first element of a level is a special checkpoint element. this can be placed wherever (unless using anitarf's initial path idea)
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" (a trivial problem if using anitarf's initial path idea)

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

[Anitarf]

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?

[Yrth]

Originally Posted by Anitarf

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.

that's true, they are. but they're pretty well worn out. even more eclectic ones like "soft escape" are getting a bit tired. besides this, a lot of the reason I'm doing this is to see if I can. if i wanted a wide audience, i would probably pick a different medium than wc3 (ooph that hurt to say)
do you still play / program for wc3 at all?

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)

they are way bigger than you imagined, but i don't think you're giving enough credit to just how much more flexible having a wide range of exits / entrances is. but if you need further convincing, i can completely eliminate the problem by altering the initial path algorithm. as you said a path from point a to point b consisting of 1x1 squares might be the best way to go. should i require this path to place (10 + rand(0, 10)) 1x1's before turning then suddenly the path will become much friendlier to your idea of a "clever" algorithm to weight the random selection of elements.

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.

yeah i could see that being a problem -- i have a few questions for you then:
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?

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?

yeah, very true -- i'm taking each of these concerns as they come (dead ends will have a reward that will be 2nd only to beating the level... specifics tbd) so if you think of any other big obstacles to fun-ness please bring them up.
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

[Rao Dao Zao]

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.

[Anitarf]

Originally Posted by Yrth

I remember that all objects (or are they called handles?) leak unless you specifically set them to null. are wc3 arrays an object?

Not sure what you mean by that. In WC3, arrays are static as declared in the script, you can't dynamically allocate them like objects.

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?

It seems to work that way, yes.

does wc3 have multiple threads? how are all clients kept to the same thread(s) (the host im guessing)?

No idea what you mean by this.

Is there anyway to directly access the data structure representing the terrain of a map?

There is a native function that lets you read the terrain type at the given coordinates, yes.

(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?

You can't declare code arrays, so you can't have code members in structs (since vJass structs are array-based). You can use function interfaces instead, which are references.

[Yrth]

Originally Posted by RDZ

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.

Hi RDZ, thanks for replying!
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"

Originally Posted by anitarf

Not sure what you mean by that. In WC3, arrays are static as declared in the script, you can't dynamically allocate them like objects.

I was saying
atomics: don't leak
objects: leak unless properly nulled
arrays of atomics: ?

Originally Posted by ani

It seems to work that way, yes.

that's horrifying

No idea what you mean by this.

does wc3 run multiple threads at once?

You can't declare code arrays, so you can't have code members in structs (since vJass structs are array-based). You can use function interfaces instead, which are references.

What, you can't make code arrays? was that on purpose?
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

JASS:

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?

[Fledermaus]

Originally Posted by Yrth

I was saying
atomics: don't leak
objects: leak unless properly nulled
arrays of atomics: ?

I don't think they leak but Ani probably knows better than me.

Originally Posted by Yrth

does wc3 run multiple threads at once?

No, only 1 thread.

Originally Posted by Yrth

What, you can't make code arrays? was that on purpose?

I think it was something to do with patch 1.24 fixing the return bug I2Code or Code2I bug that allowed access outside the VM or something.

Originally Posted by Yrth

I never really picked up interfaces, which i know i really should, so this is going to be pretty sketchy but

I'd use function interfaces:

JASS:

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 can use function interfaces with arguments as well. Check out the readme for more information.
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.

[Yrth]

Hi Fledermaus, thank you for the reply!

Originally Posted by Maus

I'd use function interfaces:
Collapse JASS:
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 can use function interfaces with arguments as well. Check out the readme for more information.
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.

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

JASS:

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

JASS:

MazeElementOneStart

I would need to pass in

JASS:

FIMazeElement.MazeElementOneStart

so at that point is there really any benefit to doing it this way? the options currently are extending the struct vs passing in this weird lambda - but totally not actually lambda thing?

i guess my new question is:
from an OOP POV, what is better?

1. A struct that has as member variables function interfaces, and, when the struct is instantiated, it takes in and assigns the member func interfaces to the appropriate static members of the actual function interface
2. An abstract struct or an interface that includes all the relevant parameters and stub methods to represent all wanted call back methods. from there every maze element will extend that abstract struct / interface and be stored and referenced as that type. they will each override the stub methods however they want.

i think the second might be better as it seems more encapsulated, but i might be able to get some non c&p code reuse out of the first so im not sure...

[Fledermaus]

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)

[Anitarf]

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.