MultiTargetPath finding path at unreachable area

General Grid graph
#1

Hey there,

Working on TowerDefense game, I’m using MultiTargetPath instead of FloodPath because in game maze dynamically created by players. Game has 4 Lane players can build their own maze at those lanes, here is the Node graph ;

Well problem is, if user completely block the lane (Target is unreachable), MultiTargetPath is ignoring Tower colliders finding a new path over Towers. I couldn’t find any function that I can check on MTP before assigning that newly calculated path to creeps. MTP setup like ;

MultiTargetPath mtp = MultiTargetPath.Construct(startPositions, target.position, null, null);
mtp.heuristicMode = MultiTargetPath.HeuristicMode.None;
mtp.pathsForAll = true;
seeker.StartMultiTargetPath(mtp, OnMultiPathComplete);

When I try to use ABPath, if player block the lane creeps were still keep moving to blocking point of lane at that position I was able to destroy blocking Towers in area with creep after couple of seconds.
Using MTP In game behavior ;

MTP on Creeps Gfycat

Using ABPath in game behavior, this is also expected behavior for MTP

ABPath on Creeps Gfycat

So my question is, How can I get same behavior with MTP as ABPath

Thanks for your time

#2

Hi

Unfortunately this is due to the way the multi target path works. If you request a path using a multi target path from multiple sources to a single target, it will internally calculate the path from the single target to multiple sources and then reverse all the paths at the end. That’s because it is only then it can share the calculations for all different paths.

What is happening now is that the multi target path will find a valid path from the target to the closest point it can reach to the units, which happens to be on the other side of the towers.

What you could do instead of completely blocking the path, you could set a high penalty (say a 1000000 which should be enough for a map your size, assuming that one tower is one world unit wide). Then the units will avoid the towers if possible, but try to walk through them if necessary (which you could detect and make them stop and attack the towers instead). Further, if the player builds two rows of towers which blocks the units, they will try to find the weak spot (say that in one case they could go make it to the target by only destroying a single tower instead of two).

#3

Also. Note that if you disable the heuristic, you will likely drastically increase the time it takes for a path to be calculated (but your graph is pretty small, so it might not matter much).

#4

Hey there,

Thanks for your reply, I’ll try as you suggest giving penalties to turrets and I will post the result, btw, my gird is 100x100 each grid is 1x1 turrets are 2x2 and the reason is why I disabled the heuristic if a player spawns a batch of creeps and then changes the graph all affected creeps follows the same path (In some scenario long path) with Sequential mode, yeah path computation is kinda takes much time without heuristic as you mentioned but it’s fine in my case. Finally if creeps are blocked they are exploding :slight_smile: and destroys towers in their explosion range , fancy explosion effect is missing right now :slight_smile:

#5

Hey there,

Well giving penalties to nodes that covered by towers failed or I made a mistake while giving those penalties. here is the code ;

...
towerSize = new Vector3(2f, 2f, 2f);
cellOffset = new Vector(0.5f, 0f, 0.5f);
AstarPath pathFinder = GameObject.FindWithTag("PathFinder").GetComponent<AstarPath>();
...

//Turret placement on cell click, cellOffset added for finding turret center.
GraphUpdateObject guo = new GraphUpdateObject( new Bounds(cell.transform.position + cellOffset, towerSize) );
guo.addPenalty = 9000000; // Tried many different values
pathFinder.UpdateGraphs(guo);

I also tried Penalty tags on seeker it didn’t changed anything, here is the results of 2 tries;

Any idea what I’m doing wrong ?

#6

Hi

Possibly you are missing the spaces between the towers. Try enlarging the bounds a bit.

#7

Wow quick reply thanks :sunny:,

Enlarging bounds could be a problem, My creeps is able to move in one cell and Player could make a maze freely, if I enlarge bounds it will also block vertical between 2 rows, but I’m gonna give a try, then I’ll be back xD.

#8

Enlarged Bounds ;

Also I didn’t mention, when I build first row of towers it works as expected.

First try, Bounds are Vector3(3f, 3f, 3f)

Second try, Bounds are Vector3(2.5f, 2.5f, 2.5f) , also it’s kinda complex maze

Third try, Bounds are Vector3(2,1f, 2.1f, 2.1f)

#9

Hi

Hm. I think you should try moving the nodes (0.5, 0.5) units so that a tower can occupy 4 cells (note that the center of a node is where the lines meet, what you see in the scene view are the connections between the nodes), otherwise there will be no way to apply the penalties in a good way.

Oh, and also. Disable guo.updatePhysics otherwise the penalty of the nodes will be reset, and if the bounds overlap, this will cause problems. See http://arongranberg.com/astar/docs/class_pathfinding_1_1_graph_update_object.php#a0ce99169ed2be7e5cf342893991513a9

#10

Hiya,

Actually my grid was like exactly what you said. All of my tries failed with that grid setup and then I tried to giving offset to grid :confused: Going back to old setup as you mentioned but it didn’t work before I’ll give it a try again.

#11

Hi

Would it be possible for you to share your project with me? Maybe I could figure out what is going wrong.

#12

Hiya,

I moved the grid as before, here is the 2 types of turrets red turrets are using colliders and crosbow turrets are using penalties and the Penalty bounds are 2.1 x 2.1 ;

#13

hi,

Well, project itself is kinda big lots of models, networking etc. I’ll strip Pathfinding then I’ll send to you, Thanks you so much for your interest.

#14

Oh, I sense Ninja editing on this post :wink: or I miss that part Well disabling updatePhysics is the trick ! :smiley: It looks much better right now only problem is placing turrets diagonally doesn’t work. See images,


Also can you link me the doc about, how can I find if my creep moved into penalized area.

Thanks for your time and I’m sorry for so much trouble.

PS! even stripping Pathfinding part on our project will take same time, probably I’m gonna create an example project about that.

[Edit]

I tried increasing bounds on GUO 2.0 to 2.75f it didn’t change anything. If I make to 3f it also blocks that horizontal 1 cell movable area between rows. And creep moves over first tower.

#15

Ah. Didn’t think about diagonal moves.
Hm… Unfortunately I don’t think that is possible to solve without hacking a bit in the core scripts.

I think this will solve it:
In the GridNode.cs script, find the Open method.

After these lines (around line 920)

GridNode other = nodes[nodeInGridIndex + neighbourOffsets[i]];
if (!path.CanTraverse (other)) continue;

PathNode otherPN = handler.GetPathNode (other);

uint tmpCost = neighbourCosts[i];

Add

if (i >= 4) {
	// Diagonal move
	// Pick the two nodes that this diagonal move will touch
	var otherA = nodes[nodeInGridIndex + neighbourOffsets[i-4]];
	var otherB = nodes[nodeInGridIndex + neighbourOffsets[(i-4+1) % 4]];
	// The denominator might need to be adjusted, but I think 4 should work
	tmpCost += (otherA.Penalty + otherB.Penalty)/4;
}

You can detect if the closest node has a penalty by using

var node = AstarPath.active.GetNearest(myPosition).node;
if (node.Penalty > 0) {
	// !!
}
1 Like
#16

hi,

It’s black magic! :blush: Works like a charm, thanks you so much for your time.

PS! I also sent an example to you via your email before saw that post.