Need some help with a path finding issue.

Sounds like this could easily be implemented with a fairly standard A* algorithm. The only difference from the basic A* most commonly encountered is that instead of measuring cost purely in terms of distance, you need to measure cost in terms of time. That is, you need to know how many resources it takes to hop from island A to island B, and how many resources an agent will receive each turn while waiting at island A. Divide the first value by the second, and that is your approximate cost: the number of turns it will take to hop from island A to island B. A* will then find the path that will take the fewest number of turns to travel.

It won't be absolutely perfect, because it ignores the effects of discrete math (it acts like 3.7 turns actually makes sense, but in reality it will take 4 turns with a few resources left over). But it will likely be close enough. And I'm pretty sure that you could easily modify your comparison later on to properly take into account non-fractional turns and leftover resources after an island hop, if the first version isn't quite optimal enough. Your cumulative costs along the path would just need to be two-part values, the number of turns, and the number of leftover resources. Comparisons between two costs would be lexicographical, comparing number of turns first, and then only comparing leftover resources if the number of turns was equal. Adding an island hop to an existing cumulative cost would also require a wee bit of fanciness, but it's basically an implementation of the core logic you already described, where the agent can use existing leftover resources, and after the island hop is likely to have a different quantity of leftover resources. It's only more complicated in the sense that it's not simply the addition of two floating point numbers, as it would be in the approximation of my first paragraph.

If the number of resources is a always small integer, as in your example, you could consider a graph where a node is an (island, number of resources) pair. The edges will tell you how you can jump to another island if you have enough resources, and how staying in the same island increases your resources. Now apply any standard path-finding technique to that graph.

I should have added that there can be up to 256 different types costs that the agent would need to take into account.

(ie: Wealth, Hunger, Water, etc)

The A* is what I'm doing now, but your approximation method sounds much better than mine :)

Hmm, with a wide variety of resources, that does get a little crazy. To get highly efficient pathing in that case, your interim path costs would have to include not only the number of turns taken thus far, but also a count of every one of the resources an agent could acquire. Then, each connection between islands needs to be duplicated for each of the resources that are consumable to make the trip. That is, if the agent can consume different quantities of gold, food, or water to get from island A to island B, there needs to be three paths connecting A to B. Each path will be specific to one of those resources.

So to determine the cost of going from A to B using gold, the code would need to look at the agent's current gold, gold acquired per turn at island A, and the cost in gold of going to island B. That determines the number of turns it will take to get to island B using gold. But in addition, you'll need to track how much food, water, and any other resource will also be acquired on island A during those turns of not traveling, as those accumulated resources might become relevant on future islands for traveling without having to wait. So your cost value will go from being just a floating point count of approximate turns, to being an integer turn count and an n-tuple of integer values of each resource type, and comparing one cost to another would be, um, awkward? You might still be best off only comparing the turn counts if they're different. But if turn counts are the same between two costs, the leftover resources would probably have to be compared based on weighted averages or something, which could consume a notable amount of CPU resources.

The heuristic might similarly need to get odd, if you are to avoid the situation of examining almost every single possible path on the entire map before deciding you found the best one. Most likely, it would need to be over pessimistic, resulting in just a non-optimal but good enough path. Whether or not this is needed is of course dependent upon how often you need to run this pathfinding and for how many agents, how many islands you have, and how many different resources can be used on average to travel between any given pair of islands. But if it turns out that you can still get acceptable performance with just Dijkstra's algorithm (A*, but with the heuristic always super-optimistically assuming cost 0 for the remainder of any path), then I guess it doesn't much matter. But since you said "a very large amount of islands", I'm guessing that's unlikely.

I should have added that there can be up to 256 different types costs that the agent would need to take into account.

(ie: Wealth, Hunger, Water, etc)

The A* is what I'm doing now, but your approximation method sounds much better than mine

A* can handle multiple factors , you just have to reduce the 'cost' to from all the attributes to single factors (some unifyiing metric) so that greater-than/less-than comparisons could be made. You can also have seperate logic for special cases (like what combinations/relations between the nodes) which BLOCK transit - which can be assessed by the factors involved (not having to have a common metric).

Edit: I should say that this is for something open source. The code that I'm sharing here is for a version of DOT that I won't be releasing until January/Febuary

Once again, this method can be extremely crude. Its just to give the AI a general path that it can fix at runtime.

All these methods sound interesting, but the conditions have changed a bit now. Islands offer both negative and positive aspects, and entities can jump backwards.

So jumping to an island foward may give 3 gold and 4 water per turn, but it takes away 2 food.

If a resource ever hits zero, the entity dies.

Entities can backtrack as far as they want in order to stay alive. So they need to remember what is behind them.

After working with what Andy said, I derived a quite nice method. The entity looks at the straight line path between where it is right now, and its final objective. From there it sums all the (positive and negative) costs.

Working backwards, it figures out where blockages (That is to say Islands it can't jump between with the attributes it would have at the time) may be, and saves that as critical points. Blockages are found by comparing the positive sum from Start to Point X to the negative sum of End to Point X.

PositiveScore is basically the A* Score function.

The first itteratation returns the critical points between where it is now, to where it wants to be. Every itteration after that is computed over the critical point.

Start -> Objective

Start -> Critical -> Critical -> Objective

Start-> Critical_2 -> Critical_2 -> Critical_1 -> Critical_2 -> Critical_1 -> Objective

Its just normal A* still but slightly twisted. Some source code:

TContainer<IndirectAd> IEntityGroup::Plan(short Index, AdvertisementBase *Goal, TContainer<UNibble> ReferenceTableSum)
{
    TContainer<IndirectAd> SolutionSet;

    //The summation of all advertisements we've confirmed so far
    TContainer<CostBase> NeededAttributes = TContainer<CostBase>(ReferenceTableSum.size());
    int m = 0;
    for (int i = BlockSize * Index; i < BlockSize * (Index+1); i++)
    {
        NeededAttributes[m].Value = RuntimeBody[i].Value;
        m++;
    }


    //TOOD: Get local islands from the world structure (In this case, the islands along the path)
    TContainer<AdvertisementBase*> LocalAds;

    bool Finished = false; //When this is true, all of the needs for my objective have been met.
    while (!Finished)
    {
        int i = 0;
        //The value cannot get greater than -1
        float Lowest = 1;
        UNibble index = 0;

        //Cycle through all the local goals. See what score is the lowest from after this advertisement -> Destination. Basic path finding
        for (AdvertisementBase * CurrentAd : LocalAds)
        {
            float AverageScore = 0;

            auto NeededTemp = NeededAttributes;

            //Go through every positive cost. Do not worry about negative effects right now. Thats managed as error correcting
            for (const CostBase & CurrentCost : CurrentAd->GetPositiveEffects())
            {
                //How much does this add increase our attributes by?
                NeededTemp[ReferenceTableSum[CurrentCost.GlobalAdr]].Value += CurrentCost.Value;
            }
            //Does this ad let us meet the requirements?
            for (const CostBase & DestinationCost : Goal->GetNegativeEffects())
            {
                Gradient grad = TemplateBody[ReferenceTableSum[DestinationCost.GlobalAdr]];
                grad.Q3 = DestinationCost.Value; //Anything that would throw us over the value is rated to be negative

                AverageScore += Scoring::PositiveScore_Linear((float)NeededTemp[ReferenceTableSum[DestinationCost.GlobalAdr]].Value, (float)DestinationCost.Value, grad); //Find the score between our destinatin cost, and our temporary attribute value
            }
            //Divide by the full size
            AverageScore /= Goal->GetNegativeEffects().size();

            if (AverageScore < Lowest)
            {
                //Its our new lowest score, so lets change the value of Lowest
                Lowest = AverageScore;
                index = i;
            }
            if (AverageScore <= 0)
            {
                //We've finished the chain. More than half of the needs are met. They rest are computed during runtime to allow for some dynamic response.
                index = i;
                Finished = true;
                break;
            }
            i++;
        }

        /*Queue is not an order dependent list. Infact, after running the plan function, it is suggested that Queue be ran through a more extensive
            scheduling function in order to retain realism.*/
        IndirectAd ad;
        ad.Address = LocalAds[index]->ReturnAddress();
        ad.TimeConstant = LocalAds[index]->TimeConstant;
        SolutionSet.push_back(ad);
        //Make sure that our summation is kept up to date
        for (auto Cost : LocalAds[index]->GetPositiveEffects())
        {
            NeededAttributes[ReferenceTableSum[Cost.GlobalAdr]].Value += Cost.Value;
        }
    }
    return SolutionSet;

}

//Note that this approximation is VERY VERY crude. Its used for distant scheduling among AIs
static float PositiveScore_Linear(float CurrentValue, float FutureValue, Gradient grad)
{
     float Q3_Factor = (float)grad.Q3 / (float)grad.Max;
     Q3_Factor *= 2;

     CurrentValue /= (float)grad.Max; //Scale the number to a  0 - 2 range
     CurrentValue *= 2;

     FutureValue /= (float)grad.Max; //Scale the numnber to a 0 - 2 range
     FutureValue *= 2;

     return (CurrentValue + FutureValue) - Q3_Factor;
}

Any opinions?