Map size, lag, and pathfinding

ID:2401154
 
Sep 24 2018, 11:02 am
Code:


Problem description:The first thing I wanted to bring up is the size of a map itself, and if there is any way to make the size of it bigger than 1000 by 1000. I'm not sure if there are many games out there with a map that big, or if even games made by large companies have them, or if they break down their maps into smaller segments.

The reason I'm bringing all this up is it seems like when I made my map bigger I started getting more lag. I haven't found anything anywhere in the code, so there is no code to post, just my observations of what causes the lag. It seems like in narrow passage ways, when the passage is blocked, but pathfinding is trying to find a way to the tile that is blocked.

I would guess that with a bigger map, there is just more area to try to find a path to a tile. If that tile is blocked in on all sides by either dense turfs or turfs with something dense in them like a dense mob, I guess path finding looks for a path pretty much everywhere on the map, and keeps going because it never finds one.



Sep 28 2018, 11:35 am
I can't tell if just lowering the map size reduced the lag or not. It seems like the lag doesn't reallt start until there is a bunch of stuff happening at one time, it could be that, and not even related to the size itself. Any ideas?
Sep 29 2018, 12:56 am
Yes. Cut the map into chunks, loading sections as you near them. That's fucking massive.
Oct 3 2018, 4:15 am
I didn't know you could load sections like that/. How do you do it?
Oct 8 2018, 9:03 am
In response to LawnMower
I don't think BYOND supports a native way of doing this. You can map your game elsewhere(like Tiled), import it into BYOND, and load it a section at a time depending on where the player is located when you're parsing it. You're going to need to know JSON for this. Maybe do 5 small sections. One would be your client's current view, and then the other 4 would be the sections directly adjacent to it. Another way would be to make your maps .jpeg files, load them all up on world startup, put the sections into a list, and load them accordingly. The drawback here being that you'd have to handle all collisions and whatnot.
Oct 8 2018, 7:36 pm
View size would influence smoothness
How many things are stacked on turfs within view
Lots of Filters
Inefficient code elsewhere
Overriding Move() or Bump() when pixel movement is used.
Oct 9 2018, 12:59 am
You can increase the size of the map to greater than 1000x1000, and you have been able to do this for years. You can even edit DMM files larger than 1000x1000 in Dream Maker. Fair warning, this is not supported behavior.

Here's a piece of code that will generate a DMM file that can be any size you want.

client
    verb
        genBlankDMM(w as num|null,h as num|null,d as num|null)
            set hidden = 1
            
            if(!(w&&h&&d)) return
            if(fexists("tempworld.dmm")) fdel("tempworld.dmm")
            var/f = file("tempworld.dmm")
            
            if(isfile(f))
                text2file("\"a\" = ([world.turf],[world.area])",f)
                
                var/i
                var/list/l = list()
                for(i in 1 to w)
                    l += "a"
                var/sequence = jointext(l,"") //build a line of pops
                
                l = list()
                for(i in 1 to h)
                    l += sequence
                sequence = jointext(l,"\n") //build a block of pops from the lines
                
                for(i in 1 to d) //write a series of blocks to the file.
                    text2file("\n(1,1,[i]) = {\"\n[sequence]\"}",f)


1) Compile an empty project with this code in it.

2) Run.

3) Right click on the title bar. client->Command...

4) In the command prompt, enter: "genBlankDMM 1024 512 16" to build a DMM file with the dimensions 1024x512x16.

5) Close dream seeker.

6) Dream Maker ->File->Open project folder.

7) Copy "tempworld.dmm" to your game's folder.

8) Open your game's DMM. Copy and paste your existing map into the larger one wherever you want.


A few warnings: Do not exceed a total number of turfs greater than about 16 million (4096x4096x1, 2048x2048x4, 1024x1024x16, etc). DS/DD are more than likely to crash before you even reach 16 million.

Exceeding 65K unique pops is probably going to corrupt your map. My best advice is to never put more than one Z layer in a single map, and also to try to split your maps up into chunks and merge them later in case of corruption.

Also, the way that Dream Maker draws the layer preview in the map editor samples every single turf on the z-layer, rather than sampling from every pixel on the preview, so the more turfs you have, the longer it's going to take for the preview to render and the shittier it's going to be to work on a map of this size.

Dream Maker takes progressively longer to load larger maps. It was never designed to handle huge maps. Buyer beware.
Oct 9 2018, 1:07 am
The reason I'm bringing all this up is it seems like when I made my map bigger I started getting more lag. I haven't found anything anywhere in the code, so there is no code to post, just my observations of what causes the lag. It seems like in narrow passage ways, when the passage is blocked, but pathfinding is trying to find a way to the tile that is blocked.

I would guess that with a bigger map, there is just more area to try to find a path to a tile. If that tile is blocked in on all sides by either dense turfs or turfs with something dense in them like a dense mob, I guess path finding looks for a path pretty much everywhere on the map, and keeps going because it never finds one.

This is exactly the problem. The built-in pathfinding solution is naive and should not be used by any large-scale project.

In most cases, a BDA* solution with a maximum target distance failure ejection case will be enough to prevent this problem. Even if it's slower best-case, the speed gains from not searching the whole map in worst case will more than justify it.

Oct 9 2018, 10:59 pm
If you're going to implement any kind of A*-related system, I can't recommend heaps highly enough. In SotS II there's a homegrown system I use that uses list items in pairs, and the "open" and "closed" node lists for the algorithm are kept in a min-heap. Because A* is all about always choosing the least expensive option from the list, a min-heap is exactly what you need for that.
Oct 11 2018, 3:58 pm
Also, You might want to keep an eye out initialized turf variables, ensure turfs that don't utilize certain variabless, does not have those variables initialized/defined.