Explanation on how velocity is used

[AudriusButkevicius]

So if I follow the most basic explanation of A*, it usually talks about finding a path from A to B on some grid/graph G.

I am completely lost where the velocity comes in here, how I should use it, and what I should set it to for the basic case of simply finding a path.

I assume it has something todo with declaring the cost of moving from P1 to P2, so that you optimise the path with the lowest cost (fastest path, etc), but what does that mean for finding a path, what does setting maximumVelocity actually do?

[AudriusButkevicius]

Also, the concept of distance being in meters is confusing.
Not all path finding scenarios translate to real world, namely in my board game, meters makes no sense, but generic "Units" would, but then velocity and the notion of time doesn't make much sense, either.

I guess in the general case all of these things should be set to 1?

Also, I assume the intent of Velocity is to declare how many units (meters) you can move in a single step, where I guess a single step is a second???

[roy-t]

Hey @AudriusButkevicius , thanks for your questions, I'll try to explain below. If you have more questions please feel free to re-open the ticket, I usually close tickets with questions immediately to keep things tidy, as I'll often forget to do it later :).

You're right that A* is a general algorithm for path finding along a graph. Indeed in general A* there is no notion of velocity, or distance. There is just a cost attached to each path.

In my library I've tried to make the cost of a path less abstract. By using units from the physical world.

So if there is a path from node A to node B and they are 100KM apart and the speed limit on this road is 50KM/H and your agent is in a car that can reach 50KM/H the cost of moving over this path is 2 hours. If your agent is on a bike their might be able to only sustain 25KM/H so the same path costs 4 hours for them. (This last part, the speed difference between a bike and a car is the maximumVelocity mentioned in the example.)

In find that for many of my users this makes it a lot easier to reason about path finding as they find it hard to make the translation from their game world to the abstract world of path finding.

Of course not all path finding scenarios take place in something that resembles the real world. Your example of a board game is
a great example. In that case you would have to be more imaginative with your values to get to the costs you want. If that is not desirable you can try an older version of this library or another one.

[AudriusButkevicius]

I am still not sure I follow what maxVelocity changes in the example between bike and car. Presumably the path is still the same? So I am lost to how one would use these. I guess you are saying the car could take some other, longer path, as long as the speed limit was higher?

I'd still think an example where all of these examples are translated to a simple board game would be helpful, because for people solving simple problems, having to specify these values really throws them off.

I also have a specific example I am trying to solve, to which I am not certain how I'd use the library.

I have a 100x100 game grid.
I have a unit, that can "teleport" up to 5 units of euclidean distance, in any, including diagonal and non-linear direction, even if there are obstacles in the way, or if there even no "walkable" path.

Can this library be used for a problem like that?

As far as I understand, I could just generate nodes with for each point of the grid, and then from any node T I would connect it to all other nodes where distance is <5, with "speed limit" of 1, and do a find operation with maximum velocity of 1?

I guess the path will be right, but the rest will be some non-sense numbers, that I don't care about anyway?

[roy-t]

" I guess you are saying the car could take some other, longer path, as long as the speed limit was higher?"

Exactly, the cost of the path is time, so the 'cheapest' path could be different for actors with different top speeds.

As for your example it would not work easily with this library. As it takes the distance between nodes into account so jumping wouldn't work well. In a plain A* library it should work but would lead to a lot of edges since every node (not an edge) would be connected to 5 other nodes in each of the 8 directions. So for a 100x100 grid that would to roughly 400.000 edges.

In your case wouldn't a simpler algorithm work? I think the shortest path would always be to take as many diagonal steps as possible until you're a straight line away from your target.

[AudriusButkevicius]

Thanks for your insights.
While I have you here, and while you have expertise on the subject I'll explain my scenario in more details.

I gave the game board as an example, but in reality my grid could be like this:

(blue is pathable, yellow are points to find a path between, red is optimal path).

In the top example, the shortest path is to teleport across the gap.
The second example, the gap is too big to teleport, but you can still cut corners as you go around the gap.

In reality, my grid is roughly 5000x5000 units where some cells are pathable some are not, and the maximum teleportation distance is more like 30, so I guess as you said, this would be an absurd amount of edges doing it that way.

Do you have any suggestions how to approach this?

My alternative thought was to downscale the grid.
Namely divide 5000x5000 by 15 and create a second smaller grid, and assume that if any cell in the 15x15 is pathable, mark the "supercell" as pathable.

Then find a simple path between the supercells, and hopefully find two normal sized cells within the two supercells that are both pathable and less than 30 units apart (probably closest to the desired destination?)

I suspect that might fall apart in a case where the move between the supercells is unot possible due to the smaller cells of both supercells actually being too far apart.

[roy-t]

5000x5000 is probably too much to handle if you want real-time path finding. Your idea sounds a lot like hierarchical path finding. This looks like a great article on that: https://alexene.dev/2019/06/02/Hierarchical-pathfinding.html.

As for teleportation. If you explain it like this it sounds like for path finding you can just connect the gaps that are small enough to jump over. So those parts are just connected to their nearest straight/diagonal node on the other end. Then when traversing the path you need to check if the next node is part of a gap or not. If you enter a gap start to play the jump animation.