// SPDX-License-Identifier: MIT
// Copyright (c) 2026 Incoprea
// Find a minimum-time route on a small map
// Not compiled or tested in-world
// Setup: Place in a spare owned prim. Set N2..10, START/GOAL and edge triples from,to,cost. Owner touch runs a bounded local calculation.
// Stop / restore: Disable/remove. No travel, publication, payments or external operations occur.
// Notes: Uses a simple quadratic selection loop suited to a small graph. Negative or zero edge costs are rejected.
// License: see LICENSE in this distribution.
// Original Incoprea. MIT. Local planning demonstration.
integer N=5;
integer START=0;
integer GOAL=4;
list EDGES=[0,1,2.0,0,2,5.0,1,2,1.0,1,3,4.0,2,4,2.0,3,4,1.0];
default
{
    touch_start(integer detectedCount)
    {
        if(llDetectedKey(0)!=llGetOwner())return;
        if(N<2||N>10||START<0||START>=N||GOAL<0||GOAL>=N||llGetListLength(EDGES)%3)
        {
            llOwnerSay("Invalid graph.");
            return;
        }
        integer i;
        for(i=0;i<llGetListLength(EDGES);i+=3)if(llList2Integer(EDGES,i)<0||llList2Integer(EDGES,i)>=N||llList2Integer(EDGES,i+1)<0||llList2Integer(EDGES,i+1)>=N||llList2Float(EDGES,i+2)<=0.0)
        {
            llOwnerSay("Invalid edge.");
            return;
        }
        list distance;
        list parent;
        integer visited;
        for(i=0;i<N;++i)
        {
            distance+=[1000000.0];
            parent+=[-1];
        }
        distance=llListReplaceList(distance,[0.0],START,START);
        integer pass;
        for(pass=0;pass<N;++pass)
        {
            integer best=-1;
            float bestCost=1000000.0;
            for(i=0;i<N;++i)if(!(visited&(1<<i))&&llList2Float(distance,i)<bestCost)
            {
                best=i;
                bestCost=llList2Float(distance,i);
            }
            if(best>=0)
            {
                visited=visited|(1<<best);
                for(i=0;i<llGetListLength(EDGES);i+=3)
                {
                    integer a=llList2Integer(EDGES,i);
                    integer b=llList2Integer(EDGES,i+1);
                    integer next=-1;
                    if(a==best)next=b;
                    else if(b==best)next=a;
                    if(next>=0)
                    {
                        float candidate=bestCost+llList2Float(EDGES,i+2);
                        if(candidate<llList2Float(distance,next))
                        {
                            distance=llListReplaceList(distance,[candidate],next,next);
                            parent=llListReplaceList(parent,[best],next,next);
                        }
                    }
                }
            }
        }
        if(llList2Float(distance,GOAL)>=1000000.0)
        {
            llOwnerSay("No route under cost limit.");
            return;
        }
        list path=[GOAL];
        integer at=GOAL;
        integer guard;
        while(at!=START&&guard<N)
        {
            at=llList2Integer(parent,at);
            path=[at]+path;
            ++guard;
        }
        llOwnerSay("Route="+llDumpList2String(path," -> ")+" cost="+(string)llList2Float(distance,GOAL));
    }
}