Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Mr Crabman]

One kind of cool thing that may result from magic in some worlds is "alien geometry", or to be more descriptive, things like rooms or caves that are bigger on the inside (or smaller!), or doors that lead back into the same room, and so on. These videos have some examples:

https://www.youtube.com/watch?v=kEB11PQ9Eo8

https://www.youtube.com/watch?v=_xFbRecjKQA

You could imagine for instance:

1. A forest coated in perpetual fog, where once you enter you can't get back out again (unless you strike a deal with one of the local faeries to help you get out) because everywhere you turn you end up somewhere else deep in the forest. Bonus points if the fog and weird dimensional stuff is expanding and threatens to consume the continent in this cursed forest.

2. An ancient fortress full of strange apparitions, where you are able to make 7 right turns in a row yet still be entering new rooms each time, or fall through a trapdoor into an incredibly deep pit, but you look up and can simply climb back out a couple of meters (and it may or may not be the same place you fell from!).

3. A tower that looks fairly normal, but if you go inside and start climbing it's literally infinitely tall, and the room at the top can only be reached through its window or via teleportation (can never be reached from the staircase).

4. A really long underground tunnel from the outside, but it's only a few steps long when you go inside (ie it's shorter on the inside).

5. Chests that are far larger inside than out (maybe leading inside a mysterious large building that can't be found anywhere in the world except the chest), or perhaps even lead out of other chests if you climb in (for this to work, obviously climbing into a chest/container would need to be an action one can do).

Prime candidates for this sort of thing would be structures (or locations) made by eldritch/demonic/divine forces, or that are under the influence of such otherworldly beings (or some powerful artifact), or were the epicenter of some magical disaster/accident that may have damaged the fabric of space itself.

This feature would mostly be noticeable in adventure mode, but fort mode would be affected as well when magical disasters occur or reality warping forces/beings start to affect the fort, or if you embark in a region that is already affected, or when remotely viewing raids that occur in such a location (as remote-viewing this stuff is a planned feature).

On a programming level this would be implemented more or less way it is in other games; basically just portals (which are already a planned feature), which would be either leading to other places in the normal worldmap (usually nearby/in the same general location) resulting in weird spatial topology, or to special "pocket dimensions" that may be visually based on/look like the general area they were made from.

But what separates this from "normal" portals, is that rather than having obvious tells/visual effects (like glowing flashy borders or just being solid colors with lightning and stuff), they are seamless, to preserve the illusion properly of it being "weird space" rather than just portals. Also the end location usually (but not always) looks like it "fits in" as part of the locale.

The space that you will reach upon passing through is what should be rendered on the other side, rather than what is *actually* there according to the game engine; for instance, you don't want to be seeing a given room through the weird doorway and then be visually "teleported" to somewhere else, you want to walk in and have it feel seamless, like that's really where it leads topologically speaking. Unfortunately, for many reasons, this kind of rendering will be... Awkward to resolve, outside of adventure mode [1].

Such portals would need to be placed carefully so that you can't see the edges easily (if you can see the "real" room just around the side of the portal this kind of exposes the trick); doorways or corridors or cave entrances, or really any opening with solid edges/walls around it, are the best places to put these things. On the sides of solid walls may also be a decent location for them.

If a piece of the "wall" is mined out, it may be necessary to stretch out/change the shape and size of the portal, because with normal portals having their "gateway" damaged it makes sense to break or disable it (or just have the portal float there in midair), but we're trying to hide that it's a portal.

[1] The problem with fort mode is, say there are 2 doors on top of each other, one of which leads to a normal room, and the other to a large cave somewhere far away; you move up and down between the z-levels; what do you see behind each door during this change? How do you move the frame of reference to the cave so you can move up and down in there?

And how can you see what was actually originally behind the door? Like if you originally built your stockpile room there for instance, but then magical disaster struck and now the door leads dwarves to the caverns instead; how do you actually view the stockpile room itself, given that the game engine probably still considers it to be in the same place, just inaccessible from that angle?

For that matter, take a simple "bigger on the inside" room; say you have a large, open room, with a 3x3 column in the middle, and inside it leads somewhere way larger; how could you possibly render this? The space is already taken up by the normal room. Perhaps holes in the ground that lead elsewhere could be rendered, but anything on 1 z-level/horizontal wouldn't really work smoothly with fort mode because you see the entire level and have no real way to change your "perspective" (fixed top-down graphics really aren't ideal for this kind of thing).

In comparison, adventure mode makes this way easier because of the "fog of war" and limited field of view hiding most of the world, so you explore the cave by going in there, and you have to find the stockpile room by walking into it, and the central column room would render based on your field of view.

[PlumpHelmetMan]

+1. Considering how often non-euclidean geometry tends to pop up in speculative fiction generally, it makes a lot of sense to accommodate it in DF. Could also lead to potential for some interesting magic artifacts: eg. something approaching D&D's "Bag of Holding" (I know containers in current DF can already seem kind of like this, but IMO only until physics and in-game spaces are better ironed out).

[Magmacube_tr]

Fort mode non-euclidian doors could be presented as clickables that pan to their actual destination when pressed, and show up as a normal door, with anything that is normally supposed to be behind it all there.

Essentially, a portal. Though this solution will take away the visual magic, as the non-euclidian door will be indistinguishable at the first glance from a normal door. It would be much more immersive if both sides of such a door are seen at once.

How would fort mode handle the self-folding locations such as the foggy forest mentioned? Would a caravan or a migrant wave even come? Will anyone, especially mechants, who appear on the players map are just trapped in the forest forever? Can sending raids outside even work at all? Is the forest essentially a place of infinite map tiles?

+1 either way. This is very neat.

[Mr Crabman]

How would fort mode handle the self-folding locations such as the foggy forest mentioned? Would a caravan or a migrant wave even come? Will anyone, especially mechants, who appear on the players map are just trapped in the forest forever? Can sending raids outside even work at all? Is the forest essentially a place of infinite map tiles?

I would assume that this would depend on the reputation of the region/forest. If the local civs know that nobody ever comes back out, they probably won't send caravans or raids, and migrants would probably only be the absolute most desperate individuals who have nothing to live for on the outside, or those who are very eager to get something that is inside the forest (maybe their only family members are in your fort), or maybe those who only wandered in by accident/unintentionally were subsumed in the forest. After fort starting scenarios, maybe civs might send in people (ie your "migrants") as a form of permanent punishment/imprisonment.

Sending raids would not work unless you figure out a way to escape (ie the faeries) for them to make use of.

In some cases such locations might be an alternate dimension infinite in size (one example being that infinitely tall tower I mentioned, or maybe a demon king has an infinite castle stretching in all directions where he can enter the real world from any door), but in the specific example I gave actually was thinking it was finite in size, just wrapping in on itself (and getting larger because of the expanding fog).

Could also lead to potential for some interesting magic artifacts: eg. something approaching D&D's "Bag of Holding" (I know containers in current DF can already seem kind of like this, but IMO only until physics and in-game spaces are better ironed out).

Yeah, such a thing would almost certainly be easier than my idea as well (unless you're talking about a bag you can actually enter and walk around seeing your items strewn about; in that case it would be mostly the same idea).

[Starver]

From my time in MUDs, which basically use pointer-based 'connectivity' (even if you import/generate an array-of-array landscape), the data-structure needs revising, then pretty much any abnormal geometry can be catered for as soon as you understand it.

For simplicity, a 10x10 'block' of terrain is stored as 100 'rooms' (a tile's-worth of diggable rock or walkable-ground or flyable open-air) with N,S,E,W(,NE,SE,SW,NW,+up/down composites of all these ) exits leading to the logical neighbouring 'room' in the block (or that of the appropriate co-edged neighbouring room in the next block over). But if one or more of those tiles is to be designated as weird geometry then you modify the affected zone to feed into the pocket-universe within, deal with directional limitations[1], impose any necessary impassibilities (according to suitable game-plot-logic, like making 'diggable' walls now appear as Indistructium in the original link-grid, except for the allowable 'doorways') and arrange the pocket-universe as required (except for the entry/exit, set up impassible boundaries/world-wrapping/whatever) howeverso large it needs to appear. You could also make it hyperbolic/spherical in effective geometry, though you also need to define how this appears as (localised) layout when you have five points to the compass or potentially converging meridians.

There's a lot of really awkward code-bending needed, in most of those cases, for procedurally creation purposes. But though the original undirected-graph of 2D vectorised relationships (or 3D) between nodes is less efficient than the multidimensional array version, it gives an expandability.

(It'd possibly play merry-hell with the A* pathing-algorithm, though, if the shortest route between two points is via a change in universal reference system so that relative nearness can no longer be assumed to be usefully determined in any trivial way.)


[1] In a Doom-like engine I once dabbled with writing, I defined the ability to seperately link visual/passible/audible and even thermal effects from one open space to separate neighbours, so that you could see the room with the bonus item in it, across the (possibly non-evident) divide between spaces, but walking through it sent you into another space, sound cues (you hearing monsters, monsters hearing you) involve a potentially different 'neighboring' location, heat damage (and/or fireballs) might be another location. Having walked through the invisible portal (noting that this was pre-Portal!), to either where you expected or not, there was no guarantee that the link was bidirectional and it could be a wall (as would an indistructible window/viewscresn - wall for movement, 'linked' for vision) or be further into the maze rather than back out again or... Well, imagination was the limit. Including scale-agnosticism: going through a 6'x3' doorway that was linked to a 6"x3" doorway into the destination area would change your relative avatar size to be 1/12th the size. Aas would be obvious when you passed through whatever loop of same-size passage-to-passage links sends you back to the first room, to now apparently have a 72-foot-high doorway that you can perhaps use again to now be 1/144th your original size for... reasons. Obviously it depends on what the level-designer wanted. The plan was to have the editor do sanity-checks (reveal strange loops like this, rooms with rotational symetries of 1/2[2], re-scalings as described) but let the oddnesses remain if they were intentional. e.g. the equivalent to the Eat Me/Drink Me items in Alice's Adventures In Wonderland, or a Tardis-like interior, or a portable-/switchable-door that leads to different locations, depending upon where/how/when you move through it.

[2] It's how I started this idea off, actually. Using creative Doom WAD editing with partially-overlapping rooms that messed with spacial geometry. Nothing that went scale-bending or truly non-Euclidean (within line-of-sight) but sending two corridors across each other such that they did not link or... A favourite of mine, designing a "room" with a handy central object (pillar, stalactite, pile of boxes, whatever fitted) that you'd have to walk around twice, or more, to be back at your starting point, so that instead of (say) four possible exits, it has eight of them, in apparently similar pairs (possibly one entirely fake matting) that you'd see just one of at a time. Or maybe the door locks behind you and only by going round the central pillar twice will you find the 'original' door responds to unlocking and leads you into the next version of the area that you thought you'd just left..

[BlueManedHawk]

While I support this, it seems to me that it would be conceptually cool, but difficult to implement in a way that works with DF's level of procedural generation.

[Red Diamond]

A lot of this comes down to the limitations of procedural generation, as BlueManedHawk said.  Not discussing the limitations of procedural generation is of course what DF hype is built upon however......

A lot of this however actually is dependent upon multi-tiled creatures.  If we have to rewrite the game to support creatures with multiple tiles, then basically we are in this kind of situation already.  We would have to relativize a lot of values in the game presently used to generate sites in order to so that creatures can fit into them.  That would then allow bigger-on-the-inside mechanics to be achieved simply by reloading the site with different parameters. 

[Taras]

It may be very hard to simulate. And even harder to make AI pathfinding.

[Putnam]

It may be very hard to simulate. And even harder to make AI pathfinding.

Surprisingly, pathfinding isn't much harder with non-euclidean geometry. In fact, A* works on any arbitrary geometry, euclidean or not, no matter how many dimensions.

[Starver]

Arbitrary shortcuts complicate matters. Though the more regularly fundemental (e.g. edge-to-opposite-edge wraparound ((toroidal)) or spherical) can matter little if the A* is sufficiently prepared for the scenario, insofar as it calculates its internal metrics.

[Putnam]

Sure, there's probably schemes that make admissible heuristics non-trivial, but all that happens if you do that is that sometimes creatures will have inoptimal paths. The absolute worst-case scenario is dijkstra's aglorithm (which is essentially a breadth-first search) unless you've done something really bad.

[DwarfStar]

I think the heuristic would just need to be aware of the portals. That probably involves running A* on just the portal connections first. Note that Dijkstra is O(N^2) so probable FPS death, so not really an option in practical terms.

[Starver]

If anything, given the (practical) assumption that all agents attempting to path are strangely omniscient about the current[1] routability, way beyond what they have direct experience of, the old discussions of revamping the pathfinding with even more 'personal knowledge/assumptions' could he revived. In the case of portals (drastic, isolated examples of spooky-travel-over-distance) then maybe they needn't even be accounted for until the entity concerned has passed by the end and (theoretically, at least) looked through the Door and recognised that the other end is somewhere they know to be elsewhere. Then, for future pathfinding, they can explore the idea of Start->WormholeEntrance + WormholeExit->Destination as a compound of two route searches and then compared with a vanilla-routing[2]. Though this naturally multiplies up the efforts required if more than one such portal exists, and especially if you are considering using any and every combination (and direction) of serial wormhole usage in a single trip (A->D, A->B1+B2->D, A->B2+B1->D, ditto C1<+>C2, then A->(Bs)->(Cs)->D and A->(Cs)->(Bs)->D, for a total of 13 possible routes, but 'just' 14 component sub-routes (whose efficiencies can be potentially searched until their cost outweighs a more competitively useful combo/non-comvo).


That said, the "Tardis Zone" setup is maybe easier. Routing into the front (or back) door of the Tardis-like interior area, through its overly-capacious interior and then on back out through the back (or front) door, onwards to your destination, is a less efficient 'wormhole' than (if possible) just stepping around the zone in 'normal' space. Weird-warpage, on te other hand, 'just' needs reweighting of traditional (modified-)Manhattan distances to account for the spherical/hyperbolic geometries, and wrap-around topologies (with or without spherical aberation, etc) needs to consider the possibility of a consistant improvement of nearness metric by travelling away from the traditional vector of closerness (can be considered a broader-case of wormhole-searching, but not (necessarily) restricted to a single (or interchangable) crossing-point. Much easier with only flat, strictly-Manhattanized, toroidal continuity, but implementation details are left as an exercise for the reader, according to how you imagine your geometry to work.


Individual 'experiential mapping' methods would be interesting. Discovery of shortcuts (either weird-physics or merely corner-cutting purely-Euclidean discovered alternatives) could be interestingly organic, and word-of-mouth transfer of knowledge would be good. It might even not matter how the pathing is arrayed (or scatterplotted!), though you'd potentially need much more entity-memory reserved to contain the details (per version of personal understanding) and the chances of even getting half-way to the most efficient path being discovered is lower without forcing some precalculated understanding/revelation upon the creature(s) concerned.


Sorry, back in "loads of words, it seemed simple enough when I thought through this problem" territory, and I missed a lot of my intermediate workings-out from this, to stop it being even longer! (I nearly gave you pseudocode!). Which also means you don't know I haven't made a big error, or are unaware of some crucial proof that I definitely haven't (maybe ), so... Maybe ignore me, I'm sure it's already TL;DR;...


[1] As of the moment of starting to path. Or repath if they turn up at a key spot to find themselves foiled by that very temporary through-route actually having been closed/made inaccessible by the time they get to what was actually just a momentarily valid route, just that the moment concerned was when they were guessing which way to go...

[2] Perhaps in-breadth, e.g. "step Vanilla A* search, step toWormhole A* search, step Vanilla A* search, step fromWormhole A* search" (but if either non-vanilla is 'solved', it donates its 'turn' to the obviously unsolved partner route), to ultimately find which idea is the better. With shared visit-data, one can rule out a route of one kind that merges into a route of the other (or make co-dependent upon the final result, perhaps yet to be found, in making a comparative step-total), especially if the fromW route finds itself 'still hopeful' but lands on a fromW-visited node, just as if it had self-looped.

[Red Diamond]

As I said before, a lot of the mechanics involved are no different to modelling multi-tile physics.  The movement of a creature of multiple tiles is basically a different kind of physics to the present physics of single tile creatures only.

[Putnam]

Ironically, extra dimensions is probably easier than multi-tile creatures.