There is room for improvement on room connectors

[masonwheeler]

One question that I haven't found any good answer to in GoRogue's dungeon generation algorithms is "where do connectors intersect with the edges of the rooms they connect?" This is an important question because knowing this is necessary for the proper placement of doors.

I can think of a handful of different potential techniques to answer this question, but I'm not sure what the best solution would be. Opening this issue for discussion on the subject.

[Chris3606]

I agree there is room for improvement here, and came to the same conclusion (a few methods available but not being sure what the best solution(s) would be). First, though, I believe this may be a duplicate of (or highly related to) #76?

[masonwheeler]

Yes, it does look like a related issue.

[Chris3606]

The door placement issue has been in the back of my head for awhile. First, I will say that I'm not terribly satisfied with the overall architecture of map generation in general, and a significant refactor has been on the table for GoRogue 3.0, I'm just not entirely sure exactly how I would want to do it better. I do feel that the algorithms are a bit disconnected in terms of return types, cohesion, etc. at the moment, and could probably be designed more intuitively.

As for the door-placement problem specifically, broadly speaking there are a couple solutions I've thought about. One would be to have the connectivity algorithms themselves track when they run through already open areas of the map. RoomDoorConnector already uses this method, however it requires a good bit of internal tracking and such that I suspect is adding a bit of undesired overhead, and such a method may be trickier to implement in some other algorithms.

The other option that comes to mind is a ConnectionFinder.FindConnections button, that could do something like take an IMapView<bool>, a List<Rectangle>, and iterate around the outer edge of each rectangle and return any positions that are true in the map view -- effectively allowing you to take in an arbitrary map/list of rooms generated by the room generation algorithms and find the connection points. This would have a quite small amount of overhead (in the case of rectangle shaped or rectangle-composed rooms), and would prevent the connection algorithm from having to track itself. Unfortunately, this concept gets quite more difficult to implement if the rooms aren't rectangular, which may or may not be a huge issue but could also become troublesome.

In the case of irregular rooms, you could instead take an IMapView, a list of map areas, and a list of connections, iterate over all connection points, and detect when the connections pass into an area in the list with perhaps reasonable efficiency, but can also be irritating to deal when connections cut entirely through map areas (which can happen in the case of many connection algorithms currently).

This brings up another related issue, which is that all these algorithms would require either some caveats or post-processing on the result to account for very weird cases like when a connection path cuts through just outside of an area's bounds on its way to a different area: if # is wall, P is part of a connection path, and . is floor, a case like:

##########
#PP#######
##P#######
##P...####
##P...####
PPP...####
P##...####
###...####
##########

This case is somewhat rare, but I actually have had a user encounter it, and it makes door placement troublesome.

I'm definitely open to discussing some other ideas on the topic, as well as map generation in general, as I do believe it to be an area where the library can be notably improved.

[masonwheeler]

I do feel that the algorithms are a bit disconnected in terms of return types, cohesion, etc. at the moment, and could probably be designed more intuitively.

I didn't want to say anything but... yeah, I've had the same feeling.

RoomDoorConnector already uses this method, however it requires a good bit of internal tracking and such that I suspect is adding a bit of undesired overhead

I'm not particularly worried about overhead here, as level generation is not something that happens frequently, and if it ever gets slow enough to be noticeable, it would not be difficult to set up a background task to generate the next level while the user is playing the current one.

Unfortunately, this concept gets quite more difficult to implement if the rooms aren't rectangular, which may or may not be a huge issue but could also become troublesome.

Yeah, this is important to keep in mind as I've seen the Cellular Automata algorithm generate multiple "islands" a time or two.

This case is somewhat rare, but I actually have had a user encounter it, and it makes door placement troublesome.

Yeah, I've seen that one too and had trouble with it.

I'm definitely open to discussing some other ideas on the topic, as well as map generation in general,

Here's my best thought on the subject:

• PreciseConnectionPointSelector:

  • Take a Rectangle, either a normal room or the Bounds of an irregular map area.
  • Calculate the set of squares on each of the four sides of the Rectangle.
  • If this is the bounding rect of an irregular map area, remove all border squares that are not walkable.
  • We now have a list of four sides, with all squares that it's valid to connect to on each side.
  • When asked to provide a connection between two map areas, PreciseConnectionPointSelector determines the Direction between the Centers of the two areas' bounding rects, uses that to determine which edge to connect from for each one, selecting a random point from the set for that edge.

• PreciseTunnelCreator:

  • Starts at a starting point and draws a tunnel towards the ending point, with whatever corridor style you prefer.
  • Before drawing each point, checks to see if this point is already walkable. If so, abort tunnel generation and report the point at which you found an intersection.
  • If you're trying to draw a tunnel from room 1 to room 2, and it aborts early, you can look up the abort point, see that it's in room 3, and tell it to draw a tunnel from room 3 to room 2, which will begin from a random point along the opposite edge of room 3 that won't necessarily line up with the one coming in from room 1, so it looks like "room with multiple connections" rather than "room that got a corridor laid across it."

This wouldn't fix the "cutting along the edge of a wall" problem--getting that right would require additional complexity--but it should help a lot with the rest of it.

[Chris3606]

This looks like a pretty good stab at it. I will be tied up with real life stuff for the next week or so that will prevent significant development time, but when I next get a chance I'll look into it. It definitely seems like something that causes a degree of breaking change such that it would end up waiting until 3.0 anyway, so there should be some time to experiment. Thanks for the input, always open for more!

[Chris3606]

A few notes I've thought of:

I'm not particularly worried about overhead here

I agree at least to a point, as slow map gen is something that, as you suggested, is much more dealable than slowness in other portions (pathing, for instance). This is somewhat evident in the current code where in map generation I'm much more apt to using things like System.Linq to make more succinct code at the cost of a bit of performance than in other places where performance absolutely matters. That much said, if it comes to something bit like going from an O(n) operation to O(n^2), that can still be an issue as the map size scales up. I don't think that type of thing will be necessary for tracking purposes, given that even MapArea has O(1) Contains function, however it would be something that will become evident when playing around with it.

When asked to provide a connection between two map areas, PreciseConnectionPointSelector determines the Direction between the Centers of the two areas' bounding rects, uses that to determine which edge to connect from for each one, selecting a random point from the set for that edge.

There is similar (though somewhat disparate) functionality provided via the current connection point selectors, where you have options to use the center of the bounding box or some other metrics to select the connection points used to connect two rooms. The Direction determining edge functionality is unique, however it is worthy of note selecting connection points off the center may actually not work very well if the map areas are of very irregular shape. I leveraged existing connection methods in DungeonMazeGenerator, for instance, and ran into a number of issues where when map areas represented tunnels, selecting things based on the center point broke horribly. Similar issues may apply to concave map areas, although they would be limited in effect by your concept of knowing which points are valid connection points on a per-side basis. That much said, I am wondering if keeping multiple options here is actually still useful for working with odd cases like that.

In general, were these two options conceptualized as a replacement for any particular algorithm/set of algorithms currently in map generation, or as an addition to the current connection system? Disconnected as map generation is currently granted, on first glance I do want to keep multiple options for steps therein that can be switched in and out, as many map generation methods may be useful and no one system covers all cases. That much said, I absolutely think the algorithm described between these two classes is useful, and could possibly be used to unify some of the various algorithms present now without much change in functionality. In addition, the connection tracking system suggested actually works for a majority of the algorithms already in place as well.

[Chris3606]

Follow-up question to the one above. I noticed this open-source .NET library for map gen came out awhile back. It implements extensible map generation algorithms based on a map abstraction combined with a shader-pass type concept to string them together. I've been meaning to give it a thorough walk-through, however given this other library is also MIT, do you think the concept (or the library itself, for that matter) has merit for GoRogue's map gen? There are some elements of that library implementation wise that I'm not partial to personally, but even just the concept could potentially be useful?

[masonwheeler]

Hmm... the concept looks interesting. Not sure how well it would integrate with what you already have, but the "map building pipeline" is a cool idea.

[Chris3606]

That's been my conclusion thus far as well. I don't think I'd try to integrate it directly with what I have, at least as part of the core library (It would probably be possible to implement their abstractions via GoRogue's to use the two together, though).

Generally, I think their map abstraction gets a little complicated for my liking, broken down a bit too far and there's some other stuff mixed in like pathing algorithms that overlap pretty harshly with GoRogue's own stuff. That much said, I was also somewhat intrigued by the pipeline concept, and while the abstractions might be different, even a map-view based abstraction I think could potentially be used to implement that pipeline concept. Further, the algorithms I have would break up into stages fairly well -- in fact they're pretty much already broke up into stages (generation, connection, etc), but the concept isn't formalized. I think formalizing that pipeline might go a little way toward solving the organization problem.

It's probably a ways down the road, as it's obviously a very significant refactor. But it might be worth playing around with implementing GoRogue's current generation in a pipeline-esque style?

[masonwheeler]

I do like its notion of a tile-based map as a core concept. This is one thing that's always kind of bugged me about GoRogue: map generation assumes everything is a IMapView<bool>, which can only conceptually handle two tile types. (ie Wall and Floor.) I actually have a grid of tile objects containing a bunch of information, and I have to use an overlay to interact with GoRogue.

[Chris3606]

I believe this is by design/due to the current scope of what the map gen algorithms handle.

Map views were never designed to be a primitive type in a production environment, they're almost always designed to be an overlay. I don't expect a user to maintain an actual array of boolean values for FOV any more than I really expect a map to actually be stored as bool tiles. The whole point of map views is to allow GoRogue to ignore how the data is actually stored, and allow a user to conveniently provide an overlay that tells GoRogue only what it needs to know (by implementing IMapView appropriately). This leaves how users actually handle their data up to them.

GoRogue's current map gen algorithms all take ISettableMapView<bool> for no other reason than, the current map generation algorithms don't have any other functionality to offer other than placing walls and floors. I could easily change map generation to return IMapView<TileType> where you have enum TileType = {WALL = 0, FLOOR };, but it adds no functionality to do so right now because GoRogue map algorithms don't do anything but place wall or floors. The chances of me being able to define values that one doesn't have to translate to something else in the general case is pretty slim (as GoRogue as a design principal avoids caring about actual map structure in its core algorithms), so in many cases there would still be a translation layer. If that's the case, then given the current set of GoRogue map gen algorithms, returning as TileTypes or some such adds no functionality and reduces prototyping interoperability with FOV, pathing, etc.

It was always the intent, though, that map generation algorithms that dealt with some other types of tiles could be designed and included in GoRogue. It's just that actually doing it is the part that I never got around to :D. If such an algorithm was included, it would meet no objection from me to have the algorithm take an IMapView<TileType> or something, and even possibly to have the current algorithms take the same as well for consistency. I'm hesitant to get more complex than that, though, as I still want to avoid fully establishing how the map data is stored. Asserting what has to be contained within tile objects as a complex structure only reduces ease of compatibility with complex libraries (the ASCII display/game lib SadConsole is a good example of where you can run into issues here, as its typical use case establishes its own class commonly used to implement tiles, and a seperate class commonly used to implement non-tile objects).

That's actually one of the parts that bugged me about the RogueElements library linked above -- not that it used tile-based map structure (again, as long as you're making use of more than 2 values I see no issue with that, provided its abstracted properly), but rather that it didn't use tile based maps as its most basic concept -- there is a base class that doesn't even go so far as to assume a map is made up of tiles, which I found to be an excessive abstraction considering how little I could find it actually used in the code base.

That much said, offhand I see no reason why GoRogue's map gen structure couldn't be adapted to fix this issue and provided similar "pipeline" style map gen algorithms, and even in fact to integrate the concept of tiles in the primitive sense if there was a use for more than two types...

[Chris3606]

Part of this is implemented in GoRogue 3.0 with its new map generation system. The fixes to the connection algorithms themselves can be implemented down the road within the bounds of that architecture. Moving to 3.x