Will this program suit my needs?

Hi all.
I would like to use A* for moving things around a tile-based strategy game. The cost of moving into any particular tile will be extremely variable, and dependant on parameters particular to both that tile, and to the actor attempting to enter it. In essence i’d need to dynamically calculate the tile cost for each actor, before being able to determine the total path cost.

can i do that sort of thing here? Would more specifics help ?

Here’s a specific example:
A tile (basic cost 1) contains a forest (+1 to tile cost) and the unit attempting to move into it has an Outdoorsman perk, which halves forest based movement costs (so -0.5 cost), The total cost of moving into the tile therefore would be 1.5

That’s a simple example, i could come up with way more complex ones, i might endup with up to 10 factors to be considered for each of the tile and actor, (but id assume if any are supported, an arbitrary number would be.

Because of factors like these, the fastest path from A to B would often not be the shortest/direct-est one, and could differ substantially for each actor.

Can A* handle this sort of preliminary calculation before plotting out a path ?

Hi

Yes it can.

`
using Pathfinding;

public class MyPath : ABPath {
public AgentType agentType;

/** Boilerplate (almost) copied from ABPath */
public static MyPath Construct (Vector3 start, Vector3 end, OnPathDelegate callback = null) {
    MyPath p = PathPool<MyPath>.GetPath ();
    p.Setup (start, end, callback);
    return p;
}

public override uint GetTraversalCost ( GraphNode node ) {
    uint cost = base.GetTraversalCost (node);
    // Assume tag 1 is the forrest tag
    if ( node.Tag == 1 && agentType != AgentType.Outdoorsman ) { 
        cost += 10000;
    }
    return cost;
}

// Boilerplate, required for pooling to work
protected override void Recycle () {
   PathPool<MyPath>.Recycle (this);
}

}`

Then you start your path using
MyPath p = MyPath.Construct (start, end); p.agentType = AgentType.Outdoorsman; // Or whatever seeker.StartPath (p, OnPathComplete);

Instead of the usual

seeker.StartPath (start, end, OnPathComplete);

This might require some tiny modding of the default movement scripts if you are using them.

There is one thing you will need to do, open the Path.cs script and make the GetTraversalCost method virtual. Per default it is not virtual for performance reasons (it is called A LOT during pathfinding).

Be careful with reducing cost for movement since the algorithms cannot handle negative costs, if you want to reduce the cost for say a specific unit, it is often better to increase the cost for all other units instead (which is roughly equivalent).

i notice with some concern, AgentType.Outdoorsman there. Is that implying i’d have to create some sort of cost profile ?

These cost alterations, by my design, would come in the form of perks/skills (like from a skill tree), and an agent could have many of them, not merely one. Generally what i’m thinking of is storing the cost factors of each tile as an array, and an agent would need to read that array, compare it with its own cost-reduction flags as appropriate, and output a personalised cost for that tile.

I have no doubt it’s going to be performance-intensive doing things the way i want. I’ll adapt to that as necessary , but i am determined to “do it right” (for example, having the AI combine its units into armies where only common denominators among movecost modifiers would be used, and they would move and act as one agent with regards to pathfinding)

Re: Negative costs; i understand. i want to do things this way specifically to make them logical and sensical, for example no amount of outdoorsman skills would allow you to reduce the forest cost below zero, essentiall subtracting it from the equation.

And in general, i learned a funny lesson about zero-cost pathfinding from Civilization II. After you built railroads everywhere, automated units could often get stuck in infinite loops sprinting around the map because they reduced tile movement costs to nothing. I certainly won’t let movecost drop to zero, let alone below it.

Hi

Using the AgentType enum was just an example, you could store any number of parameters in the path object and run any kind of code in the GetTraversalCost method.
However if you use multithreading you need to make sure that it doesn’t use any part of the Unity API (e.g accessing transform.position or something like that) since that will cause the thread to crash (the Unity API is not threadsafe).
Also, make sure that the code is deterministic, any randomness could cause serious issues.

Btw, you should know that this is the cost for moving on a specific tile, if no penalties or tags are set, this is usually zero. The rest of the cost comes from the connections between the tiles which is set to about 1000*distance between nodes.