Print

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

[Bumber]

Square creatures already know how to path (wagons). Awfully long snakes seem like trivial pathing problem too.

Now fixed non-square ones is a problem.

I don't think wagons actually path in such a way. They use the depot accessibility map and follow a predefined route to its stationary destination. In actuality, wagons only path with their center tile. You'll see wagons rolling right through trees and narrow corridors when you visit a retired fort as an adventurer.

[GavJ]

They use the depot accessibility map. They use the depot accessibility map and follow a predefined route to its stationary destination.

So they choose a direction to go in based on a multitile relevant map of costs and restrictions?
In other words, an algorithm for multitile creature pathing.

[Bumber]

They use the depot accessibility map. They use the depot accessibility map and follow a predefined route to its stationary destination.

So they choose a direction to go in based on a multitile relevant map of costs and restrictions?
In other words, an algorithm for multitile creature pathing.

Now create a map for every possible creature dimension and keep it updated each time a drawbridge activates or wall is built. Don't forget climbing. It's not a feasible method.

[GavJ]

They use the depot accessibility map. They use the depot accessibility map and follow a predefined route to its stationary destination.

So they choose a direction to go in based on a multitile relevant map of costs and restrictions?
In other words, an algorithm for multitile creature pathing.

Now create a map for every possible creature dimension and keep it updated each time a drawbridge activates or wall is built. Don't forget climbing. It's not a feasible method.

1) Single Map, not one per creature: each passable tile keeps track of how far away it is from the nearest non-passable tile, that is all.
2) Each creature explicitly stores its narrowest and widest widths and its height for pathing purposes. As well as its squishiness.
3) Totally unsquishy creatures are only allowed to path through parts of the map deisngated as wide enough for their WIDEST dimension (allowing pivoting in any direction with no algorithmic issues or overlap at any time). Totally squishy normal creatures can path through things only wide enough for their NARROWEST dimension. In between can scale in between if relevant.
4) Even if a creature has a path, it still has to check before moving or pivoting whether temporary obstacles like small creatures are occupying that space and react accordingly, not a big deal.

For animation purposes, if a small part of a creature overlaps an unpassable tile, but the map and its squishiness say it's OK anyway, just don't display that tile, and it is abstracted as an extremity squished in around the corner, etc. If not squishy, that wouldn't make sense BUT it won't ever come up if you use widest dimension, so no problemo.

keep it updated each time a drawbridge activates or wall is built.

Very easy for just the one map. You don't even have to check any further than the radius of the largest creature on file from the drawbridge or wall for updating! I.e. a small fraction of one map each time.

Don't forget climbing.

If it proves difficult, then yes, DO just forget climbing. I.e. don't let huge things climb until you feel like getting around to it. Isn't very realistic anyway that a giant sperm whale or whatever could climb without altering the landscape.

Not that I think it would be difficult. It's just a path like before, but pretty much restricted to only EXACTLY the right radius instead of "that radius or higher".  Which should ensure that some part is in contact with the wall. Or minor variation of that rule. Worst case, you just simulate the path and project the shape along it ahead of time, still not that bad.

[utunnels]

Build a village on the back or a giant turtle.


########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################
########################################

[Bumber]

1) Single Map, not one per creature: each passable tile keeps track of how far away it is from the nearest non-passable tile, that is all.
2) Each creature explicitly stores its narrowest and widest widths and its height for pathing purposes. As well as its squishiness.
3) Totally unsquishy creatures are only allowed to path through parts of the map deisngated as wide enough for their WIDEST dimension (allowing pivoting in any direction with no algorithmic issues or overlap at any time). Totally squishy normal creatures can path through things only wide enough for their NARROWEST dimension. In between can scale in between if relevant.
4) Even if a creature has a path, it still has to check before moving or pivoting whether temporary obstacles like small creatures are occupying that space and react accordingly, not a big deal.

I'm not sure this algorithm works. Consider, for example, the case of a rigid 1x1x2 creature needing to traverse a 1xNx2 corridor. Each tile in the corridor is 1 tile away from the nearest non-passable tile. We have no way to conclude that this corridor is traversable from using the nearest-tile map.

[GavJ]

I would probably have to actually go code it to work out the exact details personally. It would probably have to do with number of sides open to air, and whether they are opposite or not as well, etc. etc.

But with even just a single integer each, for instance, you can store from 0-31 distance to nearest obstacle for all 6 directions individually at once, per tile...

[Bumber]

But with even just a single integer each, for instance, you can store from 0-31 distance to nearest obstacle for all 6 directions individually at once, per tile...

A single four byte integer (Dword.) I think the information is more manageable as the nearest obstacle in each of the 3 dimensions (two bytes for 0-31.)

We subdivide the grid in order to handle even widths (causing it to use about the same amount of memory as the 6 direction model,) then end up with a map of nearest solid tile in each dimension. Then we calculate the creature's center (which will fall on a point in the subgrid,) and the center is able to move through a point on the subgrid that fits its dimensions.

Not sure how well this works for irregular shapes though. Like the 'n' shape of a titanic sentient xXtroll fur trousersXx. You'd need to give each limb its own bounding box, or something.

[Jimexmore]

PLEASE THE ABILITY TO CLIMB CREATURES YES! YES!! YES!!!
i wanna be able to do this https://www.youtube.com/watch?v=KXr6HffNqrs to an enemy 

[GavJ]

Not sure how well this works for irregular shapes though. Like the 'n' shape of a titanic sentient xXtroll fur trousersXx. You'd need to give each limb its own bounding box, or something.

If you buy into the whole squishiness combined with minimum versus maximum dimensions thing, then shape wouldn't matter.

If you want to conceive of an "N" unfolding itself to fit through something narrow, then of course that's hella complicated. I would personally at first just say "shapes are rigid, except for abstracted squishing"