How to know the path size on CostFunction.evaluate?

[martin3361]

How to know the path size on CostFunction.evaluate?

[gonzalezsieira]

I am not sure what you mean exactly and when to populate the variable.

Your variables are created when calling successorsOf. If you include the time as a member of the state, it will contain something like this: (coordX, coordY, time).

And the transitions between a given coordinate, (x0, y0, t), and its successors will be something like:
(x0, y0, t)->(x1, y1, t+n1); (x0, y0, t)->(x2, y2, t+n2);

If I am getting this right, you mean something like starting with reset variables for all coordinates and at successorsOf of StateTransitionFunction, getting the variable value from the state, incrementing it and putting it into the successors, then using it in CostFunction to determine the cost?

At this point, when you create the successors, not only you move between coordinates, but you increase the time counter from t to t + n for all the successors. Then, inside the CostFunction, you have access to the new state, which contains (coordX, coordY, time), so you can use the time to determine if the doors are closed or not.

[martin3361]

hello, I tried that and works perfectly

only that, when the arrival delay overlaps with door being shut, I just don't add it as a valid successor, since I don't care about the cost - the coordinate is impassable.

Thanks a lot!

[gonzalezsieira]

Hi @martin3361 . The CostFunction should evaluate only the effort of moving between one point to another with independence of the rest of the path. Then the NodeFactory, which is already implemented, accumulates the cost of the transition and obtains the cumulative cost for the entire path. You don't have to do it yourself.

In your case, if you want to minimize the length of the path, you could implement a CostFunction which returns a unitary cost when there are no obstacles between the two points, and a higher cost when that path is obstructed. Hipster will do the rest for you.

I hope my answer helps. BR,
Adrián

[martin3361]

Hello, Adrian, I appreciate your feedback, but this is not what I'm asking :)

Let's put it this way: I have a 2D map of Coordinate objects, at some there is ground beneath, while at others not, some are occupied by impassable object, so in this case it is perfectly clear which Coordinates are valid successors of given Coordinate and which are not.

However on the map there are objects like doors that stay opened and shut from time to time. I know exactly when they will be opened and shut at any given point in the future.

Thing is, passing through these doors is a perfectly valid scenario, as long as they are opened.

Let's say player moves at speed 2 Coordinates per second. I do the pathfinding and the iteration comes to a given Coordinate with a door on it. Now, if I know the resolved path so far is of length 10 Coordinates, I can conclude the player will be there after 5 seconds, so I check whether that door will stay opened between 4.75 and 5.25 seconds from now (player entry and exit time from the given Coordinate), if opened, path is valid, if not, invalid.

Unfortunately getting the iterator from the Algorithm and counting the iterations seems to not work for me because it includes other iterations that are not part of the currently resolved path.

So my guess is I have two possible solutions:

1. When successorsOf of StateTransitionFunction is called, I somehow know the length of the resolved path, so I do the calculation above and based on the result include the "doored" Coordinate as valid successor or not
2. When evaluate of CostFunction is called, same thing, but assign a huge cost of that Transition, so that the pathfinder neglects this possible path in favor of other paths that have less cost.

On neither scenario I seem to be able to access the current Node and the currently resolved path length.

I also looked at the Action thing but it doesn't seem to help me, it is good for the Eight Puzzle Problem and similar, but not in my case.

I hope I managed to explain my problem :)

[gonzalezsieira]

I see the problem, what you're trying to do it is spatio-temporal path planning. Since the cost of your path depends on the time in which you are visiting some points of the map, I only see one way in which you can properly evaluate the transitions:

1. Include in your state (the coordinate) a variable to store the time in which you will be in that location, taking as reference the beginning of the path. Your state will be different if you visit the same point but in different times.
2. When you evaluate the new transitions with the CostFunction, you will know the moment in which your agent will cross the doors, and therefore if will be closed or not. If they are, that transition will have a high cost and the algorithm will prioritize other paths.

Even if you had access to the nodes to know the path lengths, you could not solve this problem without distinguishing the coordinates with the times in which they are visited, because A* would mix the paths with different timings. The search will be more complicated, but the solutions will be valid in all cases.

[martin3361]

I am not sure what you mean exactly and when to populate the variable.

If I am getting this right, you mean something like starting with reset variables for all coordinates and at successorsOf of StateTransitionFunction, getting the variable value from the state, incrementing it and putting it into the successors, then using it in CostFunction to determine the cost?

I was thinking of initially (before starting the pathfinding), doing some kind of Manhattan distance (no diagonals allowed) between the start point to the goal, to roughly estimate when the player will be at that door, but this won't work since it is highly dependent on the exact path being evaluated in the current moment. Are you referring to such kind of precalculation?

Thank you