a* without timing out? Thread - TrAInsported

I currently have an a* pathfinding model going. Presently it runs when a train is created and it picks a "target".
"target" is what i use to steer the train towards where it wants to go presently. In the final version of my AI the idea would be the target can switch when a passenger gets picked up, a new passenger spawns, at turns etc. It's the current "Goal" and the train is the "Start" in the a* algorithm.

My algorithm is nasty ugly. I am bad at algorithms, i never was taught formally about them so when i impliment them it is loops upon loops, which might ( must ) be my problem. The method itself is 100 lines long, not counting some helper methods ( distance ), though there's a lot of if's and whatnot but still... Definately over the "10-15 line MAX!" they teach in schools.

Anyways, i think my biggest issue is calculating H. I'm using the Challenge 2 map, The target is(7,1). i start at (4,3, S). a* runs to 4,4 to the W,N,E junction, then it prefers to go (5,4) ; (5,5)... towards the bottom righttown. The reason a* starts searching on rail to the S is because i have it project out from the "front" of the train. H is currently just the physical distance, so a* has to check every block in the bottom right because those are all much closer than the needer path of going to the far left of the map so their H is smaller so it tries them first.

I am thinking that if, when i create my railList, i calculate the H then and use nearby tiles to decrease scores so that it prefers paths near homes and hotspots etc, that this could alleviate the issue somwhat. However i don't think so because as soon as it gets to the bottom right town near houses it will immediately try and fill that area.

The only other thing i can think of is stop limiting its search, it finds it pretty quickly if it happens to go north the first time. Then find the first rail in the path that has more than 2 neighbors, a junction, and then set that as the target. Then do some patching of the two paths found and send it off. I had hoped to avoid doing that though but it might be necessary.

So here's the code, not sure if you'll need it or not. I'm sure there are 10's of things wrong with it and i really apologize for the loops.:

unction setTrainsPathToTarget( train, target )
  -- A* Method to get from x,y to target, expects one of OUR trains with an UPDATED x,y! --
  --print ("")
  -- print ("trying to path for train", train.ID )
  x, y = train.x, train.y
  
  --1) Add the starting square (or node) to the open list. 
  start = railList[x][y]
  start['h'] = distance(x, y, target.x, target.y)
  start['f'] = start.g + start.h
  table.insert(openList, start)
  
  --2) Repeat the following:
  stop = false
  currentSquare = nil
  while true do
    --print ("LOOP!")
    --print ("\t OpenListLength at start of loop:", #openList)
    lowestF = 100
    removeI = 0
    for i=1, #openList, 1 do  -- Look for the lowest F cost square on the open list. This is the current square.
      f = openList[i].f
      if f < lowestF then
        lowestF = f
        currentSquare = openList[i]removeI = i
      end
    end
    print( "currentSquare x, y:", currentSquare.x, currentSquare.y, currentSquare.f )
    
     -- b) Switch it to the closed list. 
    table.insert(closedList, currentSquare)
    table.remove(openList, removeI)
    
     --c) For each of the 4 squares adjacent to this current square 
    validRails = getValidRailsNearby( currentSquare.x, currentSquare.y, lastSquare)
    
    for validI=1, #validRails, 1 do
      skip = false
      foundOnOpen = false
      rail = validRails[validI]
      --print ("Checking rail at", rail.x, rail.y)
      for closedI=1, #closedList, 1 do
        --print ("\t Closed rail x, y:", closedList[closedI].x, closedList[closedI].y)
        if closedList[closedI].x == rail.x and closedList[closedI].y == rail.y then -- On closed list, stop!
          --print("\t rail was on closedList!")
          skip = true
          break
        end
      end
      if skip == false then
        if #openList ~= 0 then -- ????
          for openI=1, #openList, 1 do
            if openList[openI].x == rail.x and openList[openI].y == rail.y then -- On Open list, check for better path
              --print("\t rail was on openList!")
              foundOnOpen = true
              openRail = openList[openI]
              
              if openRail.g + currentSquare.g < openRail.g then -- This way is a better path.
                --print("\t This is a better path, fucking around with the rail")
                openRail.parent = currentSquare
                openRail.f = (openRail.g + currentSquare.g)*10
                break
              end
              break
            end
          end
          if foundOnOpen == false then -- Was not found on open list. Add to the open list, set the h, f, and parent!
            --print("\t rail was not found on openList! Adding that bitch.")
            rail['h'] = distance( rail.x, rail.y, target.x, target.y)
            rail['f'] = (rail.g + rail.h)*10
            rail['parent'] = currentSquare
            --print("\t\t added rail with x,u:", rail.x, rail.y)
            table.insert(openList, rail)
            break
          end
        else
          -- Open list was empty, this is because the first time it might be? idk i suck at this shit.
          --print("\t List was empty, adding one to spur a bit..")
          rail['h'] = distance( rail.x, rail.y, target.x, target.y)
          rail['f'] = (rail.g + rail.h)*10
          rail['parent'] = currentSquare
          --print("\t\t added rail with x,y:", rail.x, rail.y)
          table.insert(openList, rail)
        end
      end
    end 
    
    for i=1, #openList, 1 do -- Check if the target square has been added to the open list, we are near if it has!
      open = openList[i]if open.x == target.x and open.y == target.y then
        print ( "We found the path")
        stop = true
      end
    end
    if stop == true then break end
    lastSquare = currentSquare

  end
end

Hi there,

I'm not sure if I understand the problem correctly, and my A* knowledge is pretty rusty (if not worse), but I noticed a few things.
First of all, you seem to be following this tutorial (or at least you're using the same names for your variables)... so I'll use quotes from it to describe what I mean.

You're on the right track.
Your algorithm (the loops etc) looks right, but you don't stick to the formula given: F = G+H. You don't really need to set or save "f" for the rails (although, of, course, you can do so) because if you save "g" and "h" for the rails you can always get "f" by adding them together.
F = G+H basically means "the cost of this square is the cost to get from the start to this square plus the estimated cost of getting from this square to the target".
Your calculation for h is correct, but the one for g seems off:

the way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depending on whether it is diagonal or orthogonal (non-diagonal) from that parent square.

I'm a bit confused by your approach, because from what I can tell, you never set or change "g".
For example, when you add the start to the open list, you should do start.g = 0 before:

 start = railList[x][y]
  start['g'] = 0
  start['h'] = distance(x, y, target.x, target.y)
  start['f'] = start.g + start.h
  table.insert(openList, start)

... because the distance from start node to start node is 0. Then, you should update that g distance every time you look through the open nodes and update a parent. What you currently do is:

openRail.parent = currentSquare
openRail.f = (openRail.g + currentSquare.g)*10

Instead, you should do:

openRail.parent = currentSquare
openRail.g = currentRail.g + 10
openRail.f = openRail.g+openRail.h

In the same way, whenever you're adding a new rail:

rail['h'] = distance( rail.x, rail.y, target.x, target.y )
rail['g'] = currentSquare['g'] + 10 -- g is always g of parent plus 10
rail['f'] = rail['g'] + rail['h'] -- f is always g+h
rail['parent'] = currentSquare

The next thing you'll need to change is this line:

if openRail.g + currentSquare.g < openRail.g then -- This way is a better path. 

This line should never be true, unless currentSquare.g is lower than 0. Otherwise, two positive numbers added together can never be less than one of those two numbers...
Instead, the line should check if the previously calculated cost for the openRail is greater than the cost if going there from the current square. These costs are given by "f" and "g"+"h:

if openRail['f'] > currentSquare['g'] + 10 + openRail['h'] then

Bottom line is:
EVERY time you change the parent of a rail, you need to recalculate its 'g' value. This is done by getting the g value of the parent rail and adding 10 to it (because there's no diagonal movement, so we never need to add the 14).

If you've changed the above and it still doesn't work, feel free to ask again, I'll be glad to help (and will hopefully receive messages about thread updates this time...)

P.S.: Sorry I took so long to reply - I've relatively busy with other stuff again, and these forums still don't send me an email when a new thread is started :(
P.P.S.: The comments in your code suggest that you're confused as to why openList could ever by zero. This is due to the fact that in the first run, you only add "start" to the openList and then, at the beginning of the while loop, search through the open list, get the element with the lowest f (which MUST be your start element) and then remove it from the list -> voila, your list is empty. But as long as you catch this exception, as you already do, this is no problem...

Edit: One thing I forgot to say:
I think your algorithm doesn't take into account into which direction the train is facing. This can of course make the whole pathfinding useless if the train can't turn around. Unless of course getValidRailsNearby() takes this into account...
About your finding of H: I don't really know what the best approach is here. Of course you can try to avoid hotspots (because there will be more trains there) or try to go there (because there will be more passengers), but I can't really tell you what the best approach is here, because I haven't tried it. I guess you'll just need to try. Still though, I think you should first use an unbiased distance function, that simply calculates the manhatten distance to the target. Once that works perfectly, you can add a biased one...

Edited by: Germanunkol