Jack, I would set temporary destination to a distance 3-5 times of window size. that would make the agent to dodge to that direction. if not, that means there is really no way to your desired direction.

xoxos, you can find the demo app here: http://aptalkarga.com/jkilavuz/whca/

Hello raft,

I'm trying to port your code to C++.

Some interesting wonders come up.

One of which is the speed of Java code is faster than C++ code in a large map with a lot of cells.

like 40x40

I find one of the agents oscillating within a very low depth when

the agent has a current.g + transition.cost >= neighbour.g

The code goes into the empty branch, and cannot rise to a higher depth.

And finally the method grain to a halt because that agent is unable to get out of the loop.

I already use a lot of reference operator in my C++ code to avoid copying.

But still incredibly sluggish.

Is the getActualTimelessCost function just returns the f cost between a node and the final destination

with obstacles being put into consideration?

Thanks

Jack

I'm not a C++ guy so I cannot comment much about why your C++ port works slower. but I remember I read an article about that in the past, certain things are much slower in C++, if I remember correct, for example returning objects from methods is slow because objects are copied when returned (not completely sure about this, google for it)

for TimeAStar.Node.getActualTimelessCost: well, I've wrote that code many years ago:), now looked at it again, as its name suggests, it returns the actual solved A* cost from a node to another taking obstacles (unwalkable nodes) into account but not taking any other thing (time or other agents) into account.

look at Grid.calculateActualCosts() method. It's called when Grid is constructed and finds A* paths from every node to all other nodes in grid and stores them in a map for later reference. getActualTimelessCost just returns the cached value from map.

Hi raft,

Thanks for helping me out with this.

I find the reason of slow resolution of the timeastar was because the oscillation of low reachedDepth, in average,

it takes about 50-100 loops to rise one depth for one agent, so all in all, it takes about 1000-2000 loops for

a single agent to successfully find its way out by timeastar. The grid has a size of 19x17 cells.

I take your Java counterpart, even with 30x30 cells, it is really quick. I take some stats off the program, yes

it does oscillate at a low depth and gradually rising, but not as unsteadily as mine.

My C++ counterpart takes a lot of CPU cycles to complete one agent timeastar, which is really a challenging problem for me to solve.

I profile the timeastar method, and finding that if I allow diagonal movement, it takes 13 seconds to complete in one particular occasion.

If I don't, it still takes 7 seconds to complete. Urgh.... (Depth is 32 and reduced to 16)

Thanks

Jack

need a special higher level handler for this unit behavior

the pathfinding is just a basic tool and the units have to have a higher 'path' entity interaction where the path is built once and the units behave to get to the path start/join points and then are coordinated to get through in single file order (or double if the chokepoint is 2 wide etc.. - 2 paths parallel)

Hello,

I am back to this question.

When sorting the opened list with this comparator,

//! \brief A* heap comparison functor.
struct TimeAStarHeapComparator {
     bool operator()(const TimeAStarNode* node1, const TimeAStarNode* node2) {
        return std::tie(node1->total_cost, node1->id) > std::tie(node2->total_cost, node2->id);
        
    }
};

The depth level hardly elevates, it oscillates at about 10 and 11, it takes 3 secs to get there.

Is there any thing wrong with this comparator?

If I reverse the comparison operator, it does rise at a reasonable speed, but the path is inaccurate.

Any ideas?

Thanks

Jack

I finally pinned down the cause of my problem

The problem lies in the new cost of opened neighbors

I give it a 1.0f cost to every neighbor that I open surrounding the current node

It ends up with a lot of tied nodes.

It also favors the ones that I opened first.

So if the direction is opposite, and I open it first, although the two total_cost tie, it still opens the opposite node

How should I design the new cost of opened neighbors

The h score is around 50-60 units

You may assume the map is some open space.

BTW: is getActualTimelessCost gets the h cost rather than the f cost?

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Should I just consider

bool operator()(const TimeAStarNode* node1, const TimeAStarNode* node2) const {
      return std::tie(node1->total_cost, node1->estimated_cost) > std::tie(node2->total_cost, node2->estimated_cost);
}

Thanks

Jack

If I use a grid as the search space, I must precompute all the paths' g costs in advance.

Let's say I have 3600 tiles ~(a 60x60 map)

I need to have 3600*3600 = 12960000 astar computation to precalculate.

which takes a while to complete. Are there any good ways that I can speed this up, I mean,.. ehh, the client can't wait.

thanks

Jack

Hello raft,

Thanks for responding my question.

I am still having some minor problems with my TimeAStar.

What I see in your application, is that the depth does rise steadily on every occasion.

But in my case, the depth sometimes drops back to a lower level.

So 2 things could happen, I am calculating the wrong g cost from getActualTimelessCost

BTW, as my map may have negative coordinates, I am just using ids for identifying cells

But I separate 2 ids, one for time dependent, one for time independent,

time indepenent ones won't change as they are designated to which cell I am after.

The time dependent one is for sorting. So the second problem may lie in which node

I close into the closed list. I choose to close the time dependent one, so the closed list nodes

are the ones which was previously generated from the TimeAStar constructor.

So If I calculate realtime g costs, and the depth drop back, it will be too time consuming

Even with 1024 depths in your application, it just took a fraction of time to complete

in millisecond range, mine however takes seconds to complete which worries me.

Update:

Not a problem, yours exhibits the same behavior, sometimes the depth would drop.

But ha ha, the execution time does worry me, milliseconds compared to secs

Try to lower it down, report back later

Update2:

(Close Destination)

I have changed the container of reserved table from default tree maps to hash map that improve a little

~28 secs down to ~5 secs, still slow though

Update3:

I would now try to cache the real time paths....

Update4:

Profiled the getActualTimelessCost function again, finding out that it averaging takes about 0.04 secs to complete one astar computation.

If I allow 8 directional movements, including stationary, that's 9 tiles in an open space area, then it accumulates to about 0.4 secs,

If I have to iterate until a far destination is reached, it actually takes a while to complete. Therefore, the precomputation of path cost is inevitable.

Update5:

(Far destination)

After using linear maps and arrays, the astar turn over time is reduced from 0.04 secs to 0.02 secs

Cannot believe my eyes.

1163 iterations * 0.02 secs = 23 secs <<<<< C++ with no precomputations (The multiplier is the turn over time to compute the AStar cost on demand, already using arrays and linear maps)
1163 iterations * 0.000001 secs = 0.001 secs <<<<< Java with precomputations (The multiplier is the access time for the actualCosts table)

Update6:

I have changed to use a fast square root method,

http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

Now the AStar turnover time is 0.001 sec, with 1000 iterations, it takes around 1 sec.

Thanks for your time

Happy working day

Thanks

Jack