Documentation / IntelliSense support about astar HOT 5 CLOSED

Hey @rm-code,

Previous version of this library used abstract units. (A grid cell was '1' unit wide and '1' unit high.) Traversing a cell would have a cost. Also an abstract unit. The path finding algorithm tried to find a path with the lowest cost. Unfortunately it was very hard to reason how cost would affect the path, since all these abstract units are not found in real life.

Because of this the latest version uses real units. A cell has a certain size. (For example it is 10 meters wide, or maybe 2 kilometers wide, whatever fits your game) and cells are connected through edges, which go from the center of one cell, to the center of another cell. Each edge has a speed limit. You could see these edges like a road, with a speed limit. Some roads are municipal roads and some roads are highways.

This makes it easier to reason about paths in an intuitive way. A direct route over a dirt road might not always be faster than an indirect route over a highway. The path finding algorithm tries to find the path that takes the least amount of time.

In your rogue-like everything also has a size. You might be using abstract units. But I could image that a single grid cell in your game's grid can hold a large monster. So we could use a cellSize of 2 by 2 meters. Your monster might have a normal walking speed on paved ground. We could take 5KM/h (https://en.wikipedia.org/wiki/Preferred_walking_speed) as the default traversal velocity. Now some grid cells might be difficult terrain, maybe they are covered with ice. You could set the traversal velocity of these cells to a lower value. Maybe 2KM/h.

I hope this helps thinking about how you should set up this library to work for you. Does this help? Or do you have more questions? Feel free to ask them here. I will check regularly :).

from astar.

Oooh new version! Thanks Roy! "Like A Bishop, Like A Queen" best GitHub lyrics 2020.

from astar.

@roy-t Thanks for the thorough explanation, but I'm still not sure how I would translate your system to my (indeed) abstract units. Let's say I have the following situation

The Character is standing in front of a door + and wants to move to the empty tile .
C + .

Opening the door costs 3 AP, moving onto the door tile and to the empty tile costs two more AP so all in all this would cost 5 AP.

How would I set your library up to get this information? Is it possible at all?

from astar.

@rm-code ah that makes your question a lot clearer. I think I would solve it like this:

Let's think of AP as a measure for 'how many seconds it takes to perform an action'. And let's define that every tile is 1 by 1 meters long.

Traversing a normal tile costs 2 AP which is 2 seconds. So the traversal velocity of a normal tile is 1/2 meter per second. Traversing a tile that has a closed door on it takes 3AP (for opening the door) + 2AP for traversing the tile the door is on), so 5 seconds. So the traversal velocity of a tile with a closed door is 1/5 meter per second.

Using this logic the path finding algorithm will generate the fastest path, and the units make sense.

If you prefer to use cost instead of velocity you can always try downloading version 2.1.0. It is slightly less fast than this version. (see the benchmark history) but I doubt that you would notice the difference in a rogue like.

from astar.

Thank you, I'll try it out 👍

from astar.