100 Plus Great Games 2/100PLUSV2.BIN/games/SnowFight.dxr/00008_PathFinding.ls

Text File | 2002-01-25 | 4.6 KB | 210 lines

global gStartX, gStartY, gGoalX, gGoalY, gInfluence, gClosed, gOpen, gMapWidth, gMapHeight

on initSearchVar StartX, StartY, GoalX, GoalY
  gMapWidth = 22
  gMapHeight = 22
  gStartX = StartX
  gStartY = StartY
  gGoalX = GoalX
  gGoalY = GoalY
  gOpen = [0]
  gClosed = [0]
  startNode = [gStartX, gStartY, 0, pathCostEstimate(gStartX, gStartY, gGoalX, gGoalY), pathCostEstimate(gStartX, gStartY, gGoalX, gGoalY), 0]
  gOpen[1] = startNode
end

on pathCostEstimate sX, sY, gX, gY
  x = sX
  y = sY
  sum = 0
  repeat while 1
    if x < gX then
      x = x + 1
    end if
    if x > gX then
      x = x - 1
    end if
    if y < gY then
      y = y + 1
    end if
    if y > gY then
      y = y - 1
    end if
    sum = sum + 1
    if (x = gX) and (y = gY) then
      return sum
    end if
  end repeat
  return -666
end

on getAdjecentTile aNode, aDirection
  locX = aNode[1]
  locY = aNode[2]
  yay = 1
  newX = -1
  newY = -1
  case aDirection of
    1:
      if (locY - 1) < 1 then
        yay = 0
      end if
      newX = locX
      newY = locY - 1
    2:
      if ((locY - 1) < 1) or ((locX + 1) > gMapWidth) then
        yay = 0
      end if
      newX = locX + 1
      newY = locY - 1
    3:
      if (locX + 1) > gMapWidth then
        yay = 0
      end if
      newX = locX + 1
      newY = locY
    4:
      if ((locY + 1) > gMapHeight) or ((locX + 1) > gMapWidth) then
        yay = 0
      end if
      newX = locX + 1
      newY = locY + 1
    5:
      if (locY + 1) > gMapHeight then
        yay = 0
      end if
      newX = locX
      newY = locY + 1
    6:
      if ((locY + 1) > gMapHeight) or ((locX - 1) < 1) then
        yay = 0
      end if
      newX = locX - 1
      newY = locY + 1
    7:
      if (locX - 1) < 1 then
        yay = 0
      end if
      newX = locX - 1
      newY = locY
    8:
      if ((locY - 1) < 1) or ((locX - 1) < 1) then
        yay = 0
      end if
      newX = locX - 1
      newY = locY - 1
    otherwise:
      put "invalid direction"
  end case
  if not yay then
    return 0
  end if
  newNode = [newX, newY, 0, 0, 0, 0]
  return newNode
end

on needsToBeUpdated aState, aCost
  temp = 0
  if (not isThisStateHere(gOpen, aState) = 0) or (not isThisStateHere(gClosed, aState) = 0) then
    temp = isThisStateHere(gOpen, aState)
    if not temp = 0 then
      if aCost <= temp[4] then
        return 1
      end if
    end if
    temp = isThisStateHere(gClosed, aState)
    if not temp = 0 then
      if aCost <= temp[4] then
        return 1
      end if
    end if
    return 0
  else
    return 1
  end if
end

on aStarGoGoGo
  node = 0
  newNode = 0
  newCost = 0
  repeat while count(gOpen) >= 1
    node = gOpen[1]
    deleteAt(gOpen, 1)
    if (node[1] = gGoalX) and (node[2] = gGoalY) then
      put "Found the path"
      return node
    end if
    repeat with aDirection = 1 to 8
      newNode = getAdjecentTile(node, aDirection)
      if not ((newNode = 0) or (newNode = [0])) then
        newCost = node[3] + gInfluence[newNode[1]][newNode[2]]
        if needsToBeUpdated(newNode, newCost) then
          newNode[6] = node
          newNode[3] = newCost
          newNode[4] = pathCostEstimate(newNode[1], newNode[2], gGoalX, gGoalY)
          newNode[5] = newNode[3] + newNode[4]
          if not isThisStateHere(gClosed, newNode) = 0 then
            removeNode(newNode, gClosed)
          end if
          if not isThisStateHere(gOpen, newNode) = 0 then
            removeNode(newNode, gOpen)
            pushInList(gOpen, newNode)
            next repeat
          end if
          pushInList(gOpen, newNode)
        end if
      end if
    end repeat
    append(gClosed, newNode)
  end repeat
  put "No path exists"
  return 0
end

on removeNode theNode, theList
  if theList = 0 then
    return
  end if
  repeat with counter = 1 to count(theList)
    if (theList[counter][1] = theNode[1]) and (theList[counter][2] = theNode[2]) then
      deleteAt(theList, counter)
      return
    end if
  end repeat
end

on isThisStateHere aList, aNode
  if (aList = 0) or (aList = [0]) then
    return 0
    exit
  end if
  repeat with counter = 1 to count(aList)
    if aList[counter] = 0 then
      return 0
      exit
    end if
    if (aList[counter][1] = aNode[1]) and (aList[counter][2] = aNode[2]) then
      return aList[counter]
    end if
  end repeat
  return 0
end

on pushInList aList, aNode
  if (aList = 0) or (aList = [0]) then
    aList = [0]
    aList[1] = aNode
  else
    repeat with counter = 1 to count(aList)
      if aList[counter][5] >= aNode[5] then
        addAt(aList, counter, aNode)
        return 1
      end if
    end repeat
    append(aList, aNode)
    return 1
  end if
  return 0
end