LuAstar, a simple A* pathfinding class

[kikito]

He did preface it as "a simple A*..".

The algorithm would have been simpler to implement without the hardcoded parts.

[tentus]

I'd be very interested in a pathfinding algorithm that works elegantly with Love's physics objects. I've done a little work on the problem myself and been utterly disappointed with the results. Writing something efficient is much harder than I expected it to be.

[Roland_Yonaba]

The algorithm would have been simpler to implement without the hardcoded parts.

Well, as some said before, I just write it that way cause I need it to work on 2d maps... with simple rectangular tiles
But, I am always happy to learn new stuff. And you seem to be more experienced in this, so i'll be happy to have more details, epecially when you say some parts would be easier to implements ?

[kikito]

A* is a search algorithm. It needs 4 things: the initial node, the target node, a function that returns the neighbors of a given node, and a function that returns the "distance" (i.e. cercany to target) of a node. distance = 0 means that you have arrived.

All information besides that (i.e. how to calculate the distance between two nodes, where are the obstacles, etc) are details that are not really needed for it to perform its main function; that's something better left outside - the "map" object is a great candidate for topographical details.

Assuming that we have a map appropriately set up, the A* algorithm could be implemented as a function with 4 parameters. Here's how the interface could look:

Code: Select all

local map = ... -- build map, adding obstacles etc
local Astar = require 'Lib.Astar'
local path = Astar(map(1,1), map(3,2), map.neighbors, map.distance)
-- in other words, Astar is a function that takes 4 parameters: start, end, neighbours and distance

Of course, that requires a map correctly built. Here's the simplest implementation I can think of for a map that satisfies the above requirements:

Code: Select all

-- be able to do map(1,1) or map(2,3)
map = setmetatable({}, { __index = function(x,y) return {x=x,y=y} })

-- square distance
function map.distance(n1,n2)
  local dx = n1.x - n2.x
  local dy = n1.y - n2.y
  return dx*dx - dy*dy
end

function map.neighbours(n)
  -- return the nodes up, down, left and right and/or the diagonals of a given node
  ...
end

The Astar algorithm should be much simpler now that it doesn't have to deal with topographic things like "how to calculate the neighbor of a given node", etc; it can now concentrate in finding the solution. Plus it would be applicable to other kinds of maps, not only grids.

I'm not going to write the algorithm here; Robin's wikipedia entry is good enough, and I'm a bit short of time. I hope this helps anyway.

[slime]

https://github.com/philnelson/A-Star-Pa ... ng-For-Lua
https://github.com/GloryFish/lua-astar
?

[Cantide]

I think I know what he means by tile-based.

You say very true things, however, judging by the "can you make it work with love.physics" part, I assume he does not understand A*.

(For reference: see Wikipedia.)

Yeah, it's been so long since I read up on A* I've forgotten exactly how it works. It's clearly not designed to work with pixels instead of nodes.
Still, I'm curious to know how to implement a similar AI in a program that doesn't use a grid, although perhaps that should be in its own thread. ;

[Robin]

Still, I'm curious to know how to implement a similar AI in a program that doesn't use a grid, although perhaps that should be in its own thread. ;

No grid or nothing that resembles a collection of nodes? The first is easy. The latter, while possible, is incredibly hard and complicated. It requires you to build a network of nodes from the map. Anyway, another time, another thread.

[SoggyWaffles]

You could lay out a grid of nodes and when the sprite moves to the node that contains the pixel in question it moves from the center of the node to the pixel. Or some such thing.

[kikito]

Still, I'm curious to know how to implement a similar AI in a program that doesn't use a grid, although perhaps that should be in its own thread. ;

Even with a grid, hard-coding a grid on top of the algorithm isn't a good idea. You will have to "fight" with that a-star every time time you want to add anything "special": dynamic obstacles, teleporter tiles, one-way tiles, and the like. By leaving the topographical details "outside", you can deal with these issues "outside", in the neighbours/distance functions. The algorithm can remain unaltered and still work.

[Jasoco]

I'm interested in implementing this class/library/whatever into some games. It works pretty well. But I don't like how it handles diagonal movement where it cuts corners. I'd rather it move around the edge of the tile. Also, when I had two blocks catty-corner to each other, it went right through them. So apparently diagonal doesn't check adjacent blocks to make sure there's an opening.

Other than that, it'll probably be pretty useful if I make a game with point and click character movement or one with actors that need AI to get from one location to a goal. Like the theme park patrons in Roller Coaster Tycoon.