[A bit advanced ;-;] A* Problems

ID:1767899
 
Jan 21 2015, 10:42 pm
(See the best response by Kaiochao.)
 
var/MaxAISteps = 100
var/obj/Cheese = null
turf
    Floor
        icon = 'Icons.dmi'
        icon_state = "Floor"
    Wall
        icon = 'Icons.dmi'
        icon_state = "Wall"
        density = 1  
mob
    AI
        icon = 'Icons.dmi'
        icon_state = "AI"
        verb
            Run()
                set src in world
                AI_WalkTo(src,Cheese.loc,Step = 0)
obj
    Cheese
        icon = 'Icons.dmi'
        icon_state = "Cheese"
        New()
            ..()
            Cheese = src
proc
    GetH(turf/A,turf/B)     
        return 10*(abs(A.x - B.x) + abs(A.y - B.y))
        
    AI_WalkTo(mob/AI/Source,turf/Location,list/Open,list/Closed,list/NParent,Step)
        if(!Closed)
            Closed = list()
        if(!(isturf(Source)))
            Source = Source.loc
            Closed[Source] = list()
            Closed[Source]["Cost"] = 0
            Closed[Source]["GCost"] = 0
        if(!Open)
            Open = list()
        if(Source in Open)
            Closed[Source] = list()
            Closed[Source]["Parent"] = Open[Source]["Parent"]
            Closed[Source]["GCost"] = Open[Source]["Cost"]
            Closed[Source]["Cost"] = Open[Source]["Cost"]
            Open -= Source
        Source.icon_state = "Path"
        var/turf/N = get_step(Source,NORTH)
        var/turf/E = get_step(Source,EAST)
        var/turf/S = get_step(Source,SOUTH)
        var/turf/W = get_step(Source,WEST)
        var/C
        var/CCost
        if(N)
            if(!(N.density) && !(N in Closed))
                Open[N] = list()
                Open[N]["Parent"] = Source
                Open[N]["GCost"] = (Closed[Source]["GCost"]+10)
                Open[N]["Cost"] = GetH(N,Location) + Open[N]["GCost"]
                world << "[GetH(N,Location)] + [Closed[Source]["Cost"]+10] = [Open[N]["Cost"]]"
                if(!C)
                    C = N
                    CCost = Open[N]["Cost"] 
                else if(Open[N]["Cost"] <= CCost)
                    C = N
                    CCost = Open[N]["Cost"] 
        if(E)
            if(!(E.density) && !(E in Closed))
                Open[E] = list()
                Open[E]["Parent"] = Source
                Open[E]["GCost"] = (Closed[Source]["GCost"]+10)
                Open[E]["Cost"] = GetH(E,Location) + Open[E]["GCost"]
                world << "[GetH(N,Location)] + [Closed[Source]["Cost"]+10] = [Open[E]["Cost"]]"
                if(!C)
                    C = E
                    CCost = Open[E]["Cost"] 
                else if(Open[E]["Cost"] <= CCost)
                    C = E
                    CCost = Open[E]["Cost"] 
        if(S)
            if(!(S.density) && !(S in Closed))
                Open[S] = list()
                Open[S]["Parent"] = Source
                Open[S]["GCost"] = (Closed[Source]["GCost"]+10)
                Open[S]["Cost"] = GetH(S,Location) + Open[S]["GCost"]
                world << "[GetH(N,Location)] + [Closed[Source]["Cost"]+10] = [Open[S]["Cost"]]"
                if(!C)
                    C = S
                    CCost = Open[S]["Cost"] 
                else if(Open[S]["Cost"] <= CCost)
                    C = S
                    CCost = Open[S]["Cost"] 
        if(W)
            if(!(W.density) && !(W in Closed))
                Open[W] = list()
                Open[W]["Parent"] = Source
                Open[W]["GCost"] = (Closed[Source]["GCost"]+10)
                Open[W]["Cost"] = GetH(W,Location) + Open[W]["GCost"]
                world << "[GetH(N,Location)] + [Closed[Source]["Cost"]+10] = [Open[W]["Cost"]]"
                if(!C)
                    C = W
                    CCost = Open[W]["Cost"] 
                else if(Open[W]["Cost"] <= CCost)
                    C = W
                    CCost = Open[W]["Cost"] 
        if(Location in Closed)
            return
        if(!C)
            for(var/a in Open)
                if(!C)
                    world << "Set to [Open[a]["Cost"]]"
                    C = a
                    CCost = Open[a]["Cost"]
                else if(Open[a]["Cost"] <= CCost)
                    world << "Set to [Open[a]["Cost"]]"
                    C = a
                    CCost = Open[a]["Cost"]
        Step++
        spawn(10) AI_WalkTo(C,Location,Open,Closed,Step)

Long story short, i wanted to create an advanced AI, i researched it and found out about A* and so i tried it out, after a bit of research and learning this was my code in the end(i read no other source code so i had to code it while i read about it with no reference or hint of what the code should look like so sorry if its a bit sloppy) what this code is suppose to do is make a green path from AI to Cheese, its no suppose to make AI move to cheese or anything just show the green outline("Path" is a icon_state in 'icons.dmi' thats pure green) the code works great but theres a small problem, at the beginning its the AI is in a "canyon" and it fills up said canyon before going along the outside of the wall to the cave entrance and heading straight to the cheese, anyone know why its doing this, ive read and read and tried to iron it out but my attempts just make it worse, very tired atm since its 3:00AM here, but if anyone could help that would be great :)
Jan 21 2015, 11:47 pm
As a side note, I would suggest using a loop instead of using recursion. Your code will work much faster.
Jan 21 2015, 11:54 pm
Best response
I don't know much about pathfinding, but the last line is taking NParent=Step instead of Step=Step.
Jan 22 2015, 10:16 am
thanks for pointing that out, step wasnt used and neither was NParent, i accidentally left that in because i was tired, as for recursion ill try it with a loop, but i think recursion would be easier
Jan 22 2015, 10:35 am
In response to Shwb1
Recursion is more of a hassle with more problems and less optimization. I'll try to remember to look at this after my operators meeting today, if no one else gets to you before hand. I feel like a idiot when I reply off my phone.
Jan 22 2015, 3:55 pm (Edited on Jan 24 2015, 9:57 pm)
I got it to work :D i ended up with the following code:

proc
    GetH(turf/A,turf/B)
        return (abs(A.x - B.x) + abs(A.y - B.y))*(abs(A.x - B.x) + abs(A.y - B.y))
    
    GetMinFromParam(list/L)
        var/R = L[1]
        for(var/a in L)
            if(L[a] <= L[R])
                R = a
        return R
    Clear()
        for(var/turf/Floor/a in world)
            a.icon_state = "Floor"
    IsInt(a)
        if(isnum(a))
            if(a/round(a) == round(a)/a)
                return 1
        return 0
    AI_WalkTo(mob/AI/Source,turf/Location)
        var/list/Open = list()
        var/list/Closed = list()
        var/list/GList = list()
        var/list/HList = list()
        var/list/FList = list()
        var/list/Parent = list()
        var/turf/C
        var/list/Path = list()
        var/Found = 0
        var/Tick = 0
        Open[Source.loc] = list()
        GList[Source.loc] = 0
        HList[Source.loc] = GetH(Source.loc,Location)
        FList[Source.loc] = GList[Source.loc] + HList[Source.loc]
        Parent[Source.loc] = Source
        while(1)
            if(length(Open) <= 0)
                return
            C = GetMinFromParam(FList)
            Closed += C
            Open -= C
            FList[C] = 999999
            if(Location in Closed)
                Found = 1
                break
            var/list/D = list(get_step(C,NORTH),get_step(C,EAST),get_step(C,SOUTH),get_step(C,WEST))
            for(var/turf/a in D)
                if(!(a in Closed))
                    if(!(a in Open))
                        if(!(a.density))
                            Open[a] = list()
                            Parent[a] = C
                            GList[a] = GList[C]+10
                            HList[a] = GetH(a,Location)
                            FList[a] = GList[a] + HList[a]
                    else
                        if(GList[a] > GList[C]+10)
                            Parent[a] = C
            C.icon_state = "Path"
            Tick++
            if(Tick >= 255)
                Tick = 0
                sleep(1)
        while(Found)
            C.icon_state = "RPath"
            Path += C
            C = Parent[C]
            if(C == Source)
                break
            Tick++
            if(Tick >= 255)
                Tick = 0
                sleep(1)
        sleep(1)
        for(var/i=length(Path),i > 0)
            Source.loc = Path[i]
            if(Source.MoveSpeed >= 3)
                if(i < Source.MoveSpeed)
                    i = 0
                    Source.loc = Path[1]
                else
                    i -= Source.MoveSpeed
                    sleep(1)
            else
                i--
                if(IsInt(Tick/Source.MoveSpeed))
                    sleep(1)
Jan 24 2015, 11:53 pm
I made a simplistic pathfinding code in Java for my AP Comp Sci class in 12th grade. If I can find it I'd like to post it. I feel it would make this a lot quicker for you. What I see done here I know can be done a bit quicker and easier with less lines of code. I know you've fixed your issue. But, if you'd like I can search some old flash drives for it later?
Jan 25 2015, 1:11 am
sorry for the late reply but id love to look at any material that would help improve my skills :P so if you have time could you? thanks.