Adjacency list maps

ID:1338561
 
Jul 29 2013, 11:22 am
Applies to:DM Language
Status: Open
Issue hasn't been assigned a status value.
That means, maps that are stored with each tile having a list of tiles adjacent to it, instead of the map being a box with fixed dimensions

With that, you could avoid needing to have an extra z-level full of stuff like building interiors, which is just hell to manage when teleportation and area of effect shenanigans start occuring

And you could also "split" a map and later "link" it up again
This could be an interesting alternative to the "möbious-strip" maps

With some hacks you could make it entirely compatible with the current map system too
Jul 29 2013, 11:26 am
Also infinite procedural dungeons would be possible, although linking maps together again could be a bit weird to handle if tiles "collide"
Aug 5 2013, 11:54 am
I don't think this would be really practical on a per-tile basis for a number of reasons, not least of which is that view() and such would be complicated enormously.

The advantage of doing something like this by z-level, though, is that most of those complications can be accounted for by simply looking for coordinate overflow/underflow. My proposed idea along those lines would require all map linkages to be two-way, however.
Aug 5 2013, 11:57 am
Definitely, it would just be much easier to somehow be able to avoid having fully square maps, so you could construct a say, cave, without having to worry about mobs or objects ending up outside or affecting other stuff you placed around it for space reasons through some shenanigans
Aug 5 2013, 12:11 pm
Specially considering as right now every z-level has to be the same size, the möbius strip maps kinda solve the problem with that you can chunk things, but it doesnt solve the problem t hat you still need to keep people out of tiles that shouldent actually exist but they have to

Specially the big problem with the "empty tiles" is caused by the size stuff though, as you usually will have to cram everything that isnt the main map next to eachother in a separate z-level
Aug 5 2013, 3:41 pm
Another possibility would be to allow for map "zones" to be created, rectangles that might not be specifically set to a single Z-level but might just be a portion of one. That's a smidge problematic in that for view() and such you'd need to establish which zone a tile belonged to (if any) before seeking out others to connect, since it would impact which coordinates are considered out of bounds. I suppose areas could be used for that if they were assumed to be rectangular.

Still though, I think going by whole Z-levels is the easiest approach, and simplest to manage.
Aug 6 2013, 9:57 pm
I think the most interesting approach would be if the semantics were changed a bit:
Z-levels no longer have to all be the same size
Z-levels no longer need to be square
Special delete instruction that deletes a tile and leaves nothing at all where it was (like if it was on the edge of the map)
If the above call cuts a map into multiple peices, the peices should be moved to their own z-levels
Then some thing to merge them together

You could do some real cool stuff with what I just described, but I have no idea how you would implement it interally, as it could get rather damn complex
Aug 7 2013, 5:16 am
Yeah, I really see no way the rectangular prism map structure would ever be changed; it's just too much easier to work with than the alternatives. So with that in mind, joining Z-levels is really the simplest means to the end goal of seamless maps.
Aug 7 2013, 5:41 am
Yeah its probably the most sane idea, having to chunk everything would be a bit of a pain but it would atleast be simple and work
Aug 9 2013, 8:25 pm
In response to Lummox JR
Lummox JR wrote:
Yeah, I really see no way the rectangular prism map structure would ever be changed; it's just too much easier to work with than the alternatives. So with that in mind, joining Z-levels is really the simplest means to the end goal of seamless maps.

Reverse compatible method:

world.maxx is set to the maximum x of the biggest map layer
world.maxy is set to the maximum y of the biggest map layer
world.maxz is set to the maximum z of the biggest map layer

Pre v.5XX worlds would create #Z map layer objects.

New global locate format:

world
  map[] //an array of submaps
proc
  locate(var/x,var/y,var/z)
    var/submap/sm = world.submap[z]
    return sm.locate(x,y)


New map structure: Submaps.

Submaps are actually moveable atoms that maintain a list of turfs.

map
  parent_type = atom/movable
  var
    atom/loc
    width
    height
    x
    y
    pixel_x
    pixel_y
    layer
  proc
    locate(var/x,var/y)
      return src.turfs[x+y*width]


Changes this system requires:

1) layers must be relative to the root map object. Meaning any turf or movable located on a submap should add the layer of the submap to its layers before using them to render.

2) all objects in a submap should apply the submap's pixel_x/pixel_y values, and the x/y tile offset.


Uses of such a system:

1) It allows the user to create mapping systems that have multiple physical z-layers without changing overly the way that the maps work.

2) It allows the user to link maps at edges globally by positioning a submap at the edge of another map, such that there is no overlap.

3) It allows the use of jagged maps, such that there is really no reason to bother keeping all map files the same size.

4) Using multiple map files in the compiler can be used to identify z-layers by name.

5) This allows systems like a ship moving over the water on a map without the need for massively complex bigicon systems to make up for the problems with large objects in BYOND.

6) We can start indexing turfs by submap id,turf index. if we limit submaps to 65K, let's say, we can use 2 bytes to index the submap, and keep the turf limit at 3 bytes. This allows for a maximum of 1,099,511,627,776 (just shy of 1.1 trillion turfs in the world). This limit is entirely silly, so there's no real reason to even bother worrying about the upper threshold anymore.

Effectively, I think the hardest part is going to be setting up a system that inherently understands that submaps offset to the edge of another will be linked to each other. Even then, there's no reason to actually write this in yourself. We could easily write the system ourselves if big icon objects were able to overlap map edges.
Aug 10 2013, 9:15 am
@Ter13: A non-retarded way to move select turfs would be really nice, that could work