Print

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

[Andir]

I'd actually argue that knowing a bit about C before diving into C++ is a great benefit.  I'd actually recommend reading about data types, how they use memory and pointers from a C perspective, but from that point, branch into C++, reread how all that works in C++ and you'll start to understand it a little better than going straight to C++.  All this will really cost you is a few chapters of reading about C.  C++ makes C much more powerful IMHO (and people will disagree) in many ways.

[The Bismuth]

The only problem with Taxicab Geometry with regards to stone distance is that the Z-axis is not as accessibly traversable as the X and Y are.

The Taxicab Geometry can easily be extended to 3 dimensions.

--edit-- (removed off topic screaming)

[Akhier the Dragon hearted]

I'd actually argue that knowing a bit about C before diving into C++ is a great benefit.  I'd actually recommend reading about data types, how they use memory and pointers from a C perspective, but from that point, branch into C++, reread how all that works in C++ and you'll start to understand it a little better than going straight to C++.  All this will really cost you is a few chapters of reading about C.  C++ makes C much more powerful IMHO (and people will disagree) in many ways.

This sounds like a good idea. I probably have to take a class of C anyway so nothing lost in doing it anyway.

[Shades]

The only problem with Taxicab Geometry with regards to stone distance is that the Z-axis is not as accessibly traversable as the X and Y are.

The Taxicab Geometry can easily be extended to 3 dimensions.

I like how you quoted the reason why it's not good for the third dimension in DF as you posted about how easy it was to extend. It's almost like starting an idea with the perfect point why your idea is flawed

[The Bismuth]

I like how you quoted the reason why it's not good for the third dimension in DF as you posted about how easy it was to extend. It's almost like starting an idea with the perfect point why your idea is flawed

You are right, I misread Draco's post. I might have been a little tired and emotional.

[qwertyuiopas]

(and I'm talking really low level stuff here, like polling the state of the keyboard or figuring out where the mouse is, or playing a sound that isn't a default windows beep, or loading an image into memory and displaying it on the screen).

Polling the keyboard is hard? Doesn't the (win32) function GetKeyboardState do exactly that, in a single statement?

[Teiwaz]

Yes to both questions.

I'm on my way out the door right now, but compare the process in C++ (and I don't just mean "call function X" - I mean setting up the IDE and compiler, resolving cryptic link errors, including the header file, etc. And do you really think inflicting the Windows API on someone is a good idea? I mean anyone, never mind someone who is there to learn how to program.) to a more accessible platform like XNA. Inflicting the former on a beginning programmer just encourages frustration and abandonment of a project. People learning to code shouldn't go anywhere near C++ until, well, they've learned to code and are ready to focus on the technical issues of C++ specifically.

[Richards]

From a technical standpoint I think the performance issues of dwarf fortress is the greatest limiting factor in the game for the future. I like the idea of a new separately-threaded path-finding routine but all this talk won't go anywhere unless Toady gives some kind of foundation to build an path-finding routine on.

Has there been any talk along these lines? It's kind of hard to make any progress in this field until you know specifically what you need to start the "PathFinder Project". Has Toady ever been contacted seriously about this?

[TiagoTiago]

I couldn't figure out what keywords would be good to check if someone has suggested this before, i apologize if i'm repeating.

How about, after defining the regions in whatever way you think is better (convex shapes, rectangles, line of sight or whatever) you store for each region the best path to cross it coming from one neighboring region and exiting into another, and then unless the destination is inside the region, you just access the preprocessed connecting path?

edit: If you divide the map in squares/cubes (like, first you start with a single cube, then you get 8, then each of those 8 is divided into another 8 and so on until the smallest is a single tile wide), i think this could work for multiple resolutions, like you read the whole map at low resolution, then you keep increasing the resolution along the path until you get full resolution detail for the path that is gonna be used while keeping the unused areas at lower resolutions, or it might even be possible to just decrease the resolution away from the current position in a gradient so that even less data has to be loaded at any single time.

[Shoku]

I've been thinking about changing passability for awhile. It seems like if you had building destroyers tag a particular obstacle in their way from point A to B with the length of time it would take for them to reach it and just had entities capable of that kind of thing go first you could have fairly smart pathing for groups that did things like try to tunnel into the fortress. With flying enemies able to do this there could be some issues but all the enemies that would need this complex pathfinding travel in groups anyway so for the basic goal declaration they could be limited to the simplest passability behaviors in their group- then just abandon that behavior at the first combat.

Is this all reasonable?

[Beeskee]

Seems like the least cpu-intensive way is to just ask the player what paths to use. Hopefully boroughs / burrows / whatever will help with that.

[qwertyuiopas]

To simulate digging, simply path once or twice in a special mode that considers solid but digable ground to have a high cost, but traps and likely places for military and dangerous areas(within archer range) to have a higher cost as well. If it determines that digging is a viable option(based on the path, with the actual weights varying with the results of battles, so if the darves simply pump magma into the new tunnels, they generally learn to avoid it unless they lose equally as much from more direct attacks), then path a path into the fort including ground as an option, and then set diggers to dig that path, and maybe the tiles around it with the rest of the army following. For gameplay benefits, don't reveal the tunnel(just maybe the first square(s) of it, or at least the ramp) until a dwarf breaches it. Or maybe also include liquid breaches. Or just show it anyway. Best option: a setting in the init files.

With all that wandering from the point of this discussion(should have used A*, so it would have been at least the shortest path), let me put this back to at least where my post derailed it:

Asking the player should never be required. Using what is there(like processing during pauses) is a good idea, but the design must focus around the idea that such events might never happen, so treat them as bonuses that help but if they aren't present then things MUST still run smoothly, or ignore them entirely since they would likely give little gain relative to the time to add them. (I strongly believe in the first, using when present but designing with their absence in mind, and some others are adamantly set on ingoring them outright, since they can't be guarenteed to ever happen or some other reasonable reason)

[Shoku]

I am particularly thinking about the case of things like in starcraft where an ultralisk would clog a path and other units would go around to a very stupid entrance instead. If you have a condition where passing through a particular tile just statically bumps the "distance" up to a certain number  (if it was below at that point,) seems like a good way to handle cases where a unit will be making the space a potentially effective route.

You could just have every unit go making their own tunnels for whatever was closest but I think that would be horrible. Having just a set number of units per squad go a digging would be a little better. For cases other than a bunch of prime entry points this would just mean a bunch of tunnels around the optimal entry position so this seems poor as well.


"I'm not moving" is usually a panic condition that is treated like a bad thing because a disorganized crowd shoving to get through a choke point is really ugly if it happens all the time. You don't want an army lining up to fight one guy when there's something they could be fighting two steps away, but at the same time but it is quite clear that taking a longer path instead of waiting is also really bad. Making waiting okay seems like a small weight lifted off of the processor while making the running around look much more purposeful, specifically because it would be.

[tylor]

How hard is it to do pathfinding for creatures that are able to dig, or even construct bridges and ladders? For, like, some really resourceful siegers?

[Starver]

How hard is it to do pathfinding for creatures that are able to dig, or even construct bridges and ladders? For, like, some really resourceful siegers?

It needs at least modifications to the base pathing[1], if not parallel pathing trees (as previously discussed) which treat solid earth, bridgable gaps or climbable walls as appropriately high-cost travel routes[2] or limited-accumulation[3] pathway management where it's a matter of resource-based resourcefulness.

Some might consider that a whole can of worms, of course.



[1] Possibly arbitrarily finding a tunelling/bridging/laddering point and assessing paths from origin to one side and from other side to destination, and seeing if that produces a better/more possible path than straight pathing.  But unless the arbitrariness could be optimised to something rational (smallest gap between the otherwise unjoined 'inside' and 'outside' pathing trees, biased towards the gap-points most accessible to the agents' starting point/least dangerous for them to attempt) I could see high CPU pursuing, and it starts to look more and more like the other solution anyway...

[2] Which may be mitigated if the digging/bridging/laddering creatures are 'responsible' for creatures not of that ilk (e.g. under the command of a squad leader with a number of other subordinates, all of whom are currently sufficiently unable/unwilling to go another way...  When such a squad-opinion is triggered, the sappers or other engineer-like units take on leadership role (or at least swap leader/led roles with the usual head honcho) and have their usual non-walking routing difficulties offset smewhat.

[3] Within the pathing algorithm, wall can be climbed (or other appropriate method used) for only nominal cost, but each level of wall that is climbed depletes a counter (on that routing algorithm's particular logical branch) that holds the finite amount relating to 'ladders that can be used'...  Routes that run out of ladder (or bridge, or some measure of digging effort) can no longer branch over that kind of obstacle.  Of course, one has to define what priority a short but 'effort using' traversal has over an equivalent long-way-round route, and whether one continues both routes onwards beyond the obstacle, in order to cater for later diversions or traversals...  i.e.

Code: [Select]

    A B   C D   E F
   #################
>..++_+++++_+++++_++..>
   #+#+###+#+###+#+#
   #+#+# #+#+# #+#+#
<arbitrary continuation>
   #+#+# #+#+# #+#+#
   #+#+# #+++# #+#+#
   #+#+# ##### #+#+#
   #+#+#       #+#+#
   #+#+#########+#+#
   #++++++___++++#+#
   #################
           G
Given 'x' amount of bridging ability, the routes from start to finish range from completely non-bridging (down A, back B, down C, back D, down E, back F) to bridging any or all of A_B, C_D and E_F or even going via the triple-length G-bridge, which might need one, two or three bridging elements, depending on how much based on the player's own bridging materials requirements it is, but also might involve a hefty diversion southwards as part of the assesment of routing efficiency.

It might even be worthwhile for a suitably staffed unit to consider a route-finding branch which integrates the deployment down towards G with both its bridge engineers and some mining units (ignoring for now the possibility of mining across the other small gaps instead of bridging) in order to mine more bridging material to traverse even longer 'G' gaps, if known/discovered traps are found lying across the BC and DE stretches...  But that's getting complicated.  As may be the question of whether a bridging unit can bridge across a gap that has a bridge built upon it[4] but one that is currently retracted?  That might need either a modification of the building code or 'temporary' bridging types of some form that can be laid across such gaps.[/3]

[4] Also note possible future 'grappling hook' possibilities, to 'grab' raised bridges (or retracted ones, presumably retracted into the opposite side), as another non-standard routing option.  Or at least attempted, with the possibility of breaking the bridges or loosing the hooks...