Topic: 16x16 Maps (Read 5529 times)

Dwarf · « **Reply #30 on:** May 04, 2011, 05:15:03 am »

350 GHz don't mean anything on their own. Is it actually usable?

Niseg · « **Reply #31 on:** May 04, 2011, 08:06:29 am »

Quote from: Dwarf on May 04, 2011, 05:15:03 am

350 GHz don't mean anything on their own. Is it actually usable?

Not really . The fact that it's possible doesn't mean it's economically feasible for mass production. If I remember correctly it was a fairly simple processor.

Anyways as I said what need to be done is reduce the complexity of some algorithms - that will make the game run fine on any size embark.

Embark size affects the possible number of nodes in your graph .It's about 230,400 per embark square. a 16X16 embark has 59~ million possible nodes . more nodes = more number crunching and much more complicated path finding. other than that you'll have more veins ,more plants and more and more structures and creatures . This means more stuff in the data structures you have to go through.

More is not always a problem . If you approach it using a classic "divide and conquer approach" you can get some huge improvements . My simulator only does pathfinding on 32X32 maze. In one of my examples I managed to reduce a 110 step long path's complexity from 2 million iterations that it does with a simple A* to 11520 iterations using the "same" A* (added some constraints) but just finding 13 +1 subpaths length 8~ . I believe the gains on a larger map would be much greater. I can upscale my simulator to upto 256X256 easily and I believe that with a similar complexity with a longer path.

This is how my path looks like(S= start, D=dest ,*= path, O are room access points):

Spoiler (click to show/hide)

the A* path looks like this and the runtime is significantly longer.

Spoiler (click to show/hide)

Saving paths between rooms also gives good performance but even without that path caching scheme the run times are similar. The path caching algorithms ( I got a placed waypoint example in there ) also need a path smoother( I got a function that does that fairly fast) to get an optimal path .The non cacher you see above doesn't really need smoothing . It's only off by about 4 nodes from the optimal path and I didn't finish optimizing room shapes and adding the update scheme ( a critical part for this implementation).

So can DF run smoothly in a 16X16 embark? currently no, theoretically yes. Processing power is not the only factor at the moment . You have to take power consumption into account too because mobile computing is very common these days and so are computers with less computing power and memory.

Dwarf · « **Reply #32 on:** May 04, 2011, 10:22:01 am »

What we'd really need is Toady's input - his No Code Sharing At All policy is hurting performance, it seems. But ah well, that's up to him.

Niseg · « **Reply #33 on:** May 04, 2011, 01:53:21 pm »

Quote from: Dwarf on May 04, 2011, 10:22:01 am

What we'd really need is Toady's input - his No Code Sharing At All policy is hurting performance, it seems. But ah well, that's up to him.

I don't really care about Toady's code, I'll leave him to do the dirty work

. According to what I saw in DFhack headers he's doing a pretty good job . I only hope He'll take my suggestions into considerations.

You can't really suggest path finding optimizations without knowing a thing or two about the subject or a thing or two about computer programming, algorithms and mathematics. The computer simply can't really see the map... unless you teach how. I happen to like to learn and investigate stuff . I knew nothing about pathfinding before I started playing DF but with the amount of resources on the internet (along with knowing what to look for) it wasn't hard to learn. Then I started small - first some basic UI then at version 15 or so I added A* from there waypoint based path caching , path smoothing and so on. It's all about turning suggestions into code.When one person does it another can duplicate their efforts.

The algorithms I used are really basic it's all a matter of making them work for you. I concentrated on keeping the general concept the same - you call a function - it gives you a path...

anyways I went a little crazy and enlarged the maze a little to 128X128 which is 16 times more node which is comparable to going from 4X4 to 16X16 .Clicking A* freezes for a while and yields " visited nodes:7081, length= 199 iterations= 196,924,942" ( I added commas for readability) . My algorithm the same simple maze(4 squares with U access points) yielded "visited nodes:372, length= 246 , subpathes =31 iterations= 47,664 " . I bet the room with path cache is super fast because it only needs to find 2 short paths and a path on the 8X8 map.

here is the link to it I'll spoiler it so you don't accidently click on it because JS is slow and this kind of stuff will kill it . I recommend chrome if you want to open it.

Spoiler (click to show/hide)

Tahlin · « **Reply #34 on:** May 04, 2011, 03:01:49 pm »

I'm staring at this thread and all it's glorious posts. One thought pops in my head.
Why?

WJLIII3 · « **Reply #35 on:** May 04, 2011, 03:53:37 pm »

Quote from: Number7 on May 03, 2011, 03:29:10 am

a quantum computer takes advantage of a shrodingers cat situation, where things can be in multiple states at once and all that. I'll skip the lengthy explanation, but let me say, if and when we get quantum computing, one of those will be powerful enough to break military encryption in a heartbeat, a feat that cant be accomplished by every computer in the world put together (well it can, just takes a lifetime or two )

so, then you'll get your 108x108 embarks with no lag

Quantum computer really has very little to do with Uncertainty, its actually about Entanglement, a different quantum principle. However, they will be able to instantaneously perform functions of theoretically infinite complexity. So yeah...waitin on those for my superfort.

Ganondwarf · « **Reply #36 on:** May 04, 2011, 04:03:12 pm »

Quote from: Tahlin on May 04, 2011, 03:01:49 pm

I'm staring at this thread and all it's glorious posts. One thought pops in my head.
Why?

Why what? Why play on a 16x16? Because then the answer is...I HAVE NO IDEA.
I guess, just to be cool. And have near-infinite space to work with.

GreatWyrmGold · « **Reply #37 on:** May 04, 2011, 04:37:37 pm »

Quote from: Number7 on May 03, 2011, 03:29:10 am

so, then you'll get your 108x108 embarks with no lag

No, the game won't allow more than 16x16.
Oh, and quantum computers would need to be perfected first. And released to common-Joe bozos like us who play DF and don't have military contacts.

Niseg · « **Reply #38 on:** May 05, 2011, 04:13:11 am »

Quote from: GreatWyrmGold on May 04, 2011, 04:37:37 pm

Quote from: Number7 on May 03, 2011, 03:29:10 am
so, then you'll get your 108x108 embarks with no lag
No, the game won't allow more than 16x16.
Oh, and quantum computers would need to be perfected first. And released to common-Joe bozos like us who play DF and don't have military contacts.

You don't need a supercomputer to run a 16X16 embark . What you need is some code optimization and the sky is the limit (provided you got the memory). And I can prove it with a suboptimal algorithm .

I checked how long ( JS is slow had to use profiler or it crashed) the A* run on my 128X128 simulator... about 13 seconds . My algorithm used A* for 8 ms and another 6 ms for itself. . That's about 1000 times faster .The path cacher (advanced) does it in about 6ms total (2000 times faster).

The generation of the rooms from scratch takes about 90ms (automatically define rooms and access points), and 265~ ms for path cache generation between rooms . Redraw does take about half a second. The load time is about 1.5 seconds. Whatever you do don't add waypoints those use A* between them

(13-14 second of runtime).

You'll notice the penalties are not even that big if you regenerate the connection graph from scratch periodically (every 500 frames). The dwarves can then reevaluate their paths from scratch (1 room path and 1 local path)and it would take them next to no time to do. My model is also scalable . The rooms can be grouped into sub-regions, sub-regions into regions, regions into continents , continents into planets

.

EDIT: You can't reproduce the results anymore due to an A* optimization I did ( O(1) lookup if a node exists in one of lists) which made it run about 1000 times faster .

News:

Author Topic: 16x16 Maps (Read 5529 times)

Dwarf

Re: 16x16 Maps

Niseg

Re: 16x16 Maps

Dwarf

Re: 16x16 Maps

Niseg

Re: 16x16 Maps

Tahlin

Re: 16x16 Maps

WJLIII3

Re: 16x16 Maps

Ganondwarf

Re: 16x16 Maps

GreatWyrmGold

Re: 16x16 Maps

Niseg

Re: 16x16 Maps