Print

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

[Starver]

I'm afraid you misunderstood my diagram... I meant an indefinitely long diagonal corridor surrounded by rock. I'll make it clearer:
<snip>
I was afraid the tree structure wouldn't be able to efficiently represent that as one unit. A quadtree wouldn't, but if you can then that's cool.

It would from the B-line "vectorised" format.  The tree structure was just the start but after merging based upon adjacent tree-ends that are mergable (in a manner I could spend ages explaining, but won't[1]) that would end up with something not so much a classic quad-tree.

It would actually end up saying something like: "[1,1]->[4,1]:southwall; [4,1]->[14,11]:southeastwall; [14,11]->[11,11]:northwall; [11,11]->[1,1]:northeastwall", in whatever shorthand data format is required, and the ":southwall" being shorthand for what might (in reality) be something like ":{walkable,fliable}tozone<otheropenzoneID>" (when not enclosed in that direction) and ":southeast" maybe ":{diggable}tozone<undergroundzoneID>" (when that still is).  Noting that this concept of mine has subtly changed since, anyway.

edit-added-footnote: [1] Not because you wouldn't understand, but because I know I'd spend ages on it, when you can probably work it out... sorry, just re-read what I said, and was afraid it looked a bit arrogant.

[shadow_slicer]

And the cost isn't max(dx,dy,dz) (or max(abs(dx), abs(dy), abs(dz)), if one is to nitpick), but actually:
max(abs(dx), abs(dy))-min(abs(dx),abs(dy)) + sqrt(2)*min(abs(dx), abs(dy)) + abs(dz)
"straight bit plus diagonal bit plus vertical". Or at least I think so - I think movements in the "vertical diagonal" aren't possible.

I'm still not sure I understand why the metric needs to be like that. I thought the cost for diagonal movement was the same as cardinal movement (and it seems the dwarves move just as quickly in either cardinal or ordinal). Also, dwarves can't move diagonally upward? I can understand the case for staircases, but for ramps and flying/swimming creatures it seems really silly.

[Sunken]

To the best of my knowledge, diagonal movements in 2D cost sqrt(2) times as much as orthogonal ones. At least during search.

You may be right about vertically diagonal movement. I'm not sure, but I have a hunch the vertical movement actually doesn't add to the cost at all.

[Starver]

Also, dwarves can't move diagonally upward? I can understand the case for staircases, but for ramps and flying/swimming creatures it seems really silly.

I understood that as like up the following diagonal-on-the-horizontal-plane as well as ramp-traversal:

Code: [Select]

Z0  Z+1
### ##+
#^# #v#
+## ###
And I wasn't sure enough about it to say, but I thought it was possible.  I'm sure my Adventurer can do it, wandering diagonallly across landscapes) but haven't got  the game in front of me to test, right now..  (Plus Alt-Move climb at that angle, where otherwise permssable.

[Sunken]

I'm sure it's possible, even to AI dwarfs, but I'm not sure the vertical step incurs a cost

[Xgamer4]

To the best of my knowledge, diagonal movements in 2D cost sqrt(2) times as much as orthogonal ones. At least during search.

While I have absolutely no proof, as Toady is a mathematician it really wouldn't surprise me if he obeyed the Pythagorean Theorem.

[CobaltKobold]

It's funny, because a fair number of FPSs...do not cap your speed properly, and thus it is faster to proceed at an angle to your view (gi'ing you that sqrt(2) factor boost, if strafing is as fast as walking)

And yeah, no clue about the ramp travel cost-define, though it'd clearly be root2 for straight and root3 for diagonal normally...but that doesn't really model the cost right for a creature in a gravity well. (Likewise < > as 1 cost)

[Shades]

It's funny, because a fair number of FPSs...do not cap your speed properly, and thus it is faster to proceed at an angle to your view (gi'ing you that sqrt(2) factor boost, if strafing is as fast as walking)

And yeah, no clue about the ramp travel cost-define, though it'd clearly be root2 for straight and root3 for diagonal normally...but that doesn't really model the cost right for a creature in a gravity well. (Likewise < > as 1 cost)

Actually most FPS's handle it correctly. A number of engines (quake and doom based ones for example) purposefully allow this though as there was a bug back in Quake 1, that when fixed was complained about so they ended up putting in code to replicate the effect under the corrected physics engine. I think in the halflife (counterstrike) engine it is also intentional but I don't know so much about that one.

[Starver]

Actually, one could argue that there is a speed boost to "strafe-walking".  IRL.

The length of your stride is a nominal amount, and your legs also have a lateral movement that can be added to that (pythagorously) to increase the stride length.

Yes, I'm treating the ball-and-socket joint at the hip as a two-way axial joint, and discounting the entire twisting of the pelvic bone that's probably what happens.  And if you avoid all that, how you do it (and the presumed maximum speed you're attempting) without tripping over ones own feet, is another matter, as well as the fact that there's an energy cost and soft upper limit to moving the mass of your legs along the longer diagonal (which is not 45°, so won't give you strict root(2) 45° movement for the cost of unit forward motion) and the fact that the lateral muscles probably aren't as strong and various other issues...

But apart from that, one could argue that there's a speed-boost.

[CobaltKobold]

Doesn't make your leg any longer 

[zchris13]

Doesn't mean this project is getting any closer to completion.

[shadow_slicer]

It's probably getting closer. It's just now we've debated and discussed quite a few issues. Probably everyone is just thinking carefully about what was said and weighing the advantages and disadvantages of the methods discussed.

Besides, it's not like development occurs on the forums. (After all Toady seems to do quite a bit of development, but is on the forum less than most...).

As for me, I've played around a little bit with the code numerobis posted earlier. I made the following changes:

• changed to use SConstruct to build (since I couldn't use the build script provided)
• made some modifications so it would compile
• changed the grid to support multiple tile types (other than just passable): now we have to have stairs and ramps to go up and down, instead of flying everywhere...
• changed the A* algorithm to match the one on wikipedia and adapted it to use a heap and hash set for fringe and visited respectively
• changed the A* algorithm to return both the path cost and the path
• some other bug fixes and changes that I'm probably forgetting to mention
• Generated a few more test cases

For the curious, my code is available on my personal webspace, though it's still in-progress. Next task will probably be the hierarchical stuff, which I'm still planning out.

[zchris13]

Cool. Thanks for answering my unspoken question.

[Starver]

Doesn't make your leg any longer 

Ok, I wandered offtopic a bit, but I should point out that leg length isn't an issue.  People with shorter legs don't hover, after all.  Larger subtended angles just means a lower centre of body mass during the stride.  (And awkwardness of stride, at extreme examples, just to auto-pedant myself.)

Ontopic: I've fallen foul of my usual development hell, in that I've been messing around with my own solution (no, not the "trinary tree" bit, but a bit of hand-coded TCZ-like bit 'after' that) but got stuck on minutiae and got diverted on the thought of "I know, I'll covert one of my active forts into a testable map".  I'm glad to see that practical efforts have progressed despite me.

[qwertyuiopas]

Why not a SPZ(Single Path Zone) to complement the TCZ. It would cover any area with exactly two exits, and cache the fastest path between them. Pathing within it would use A*.