Pathfinding between nodes

How do you make a simple pathfinding algorithm in lua? Let's say I have a map with "nodes", a list of connections between them and the travel time per connection and the extra time per node:

Spoiler

local map =
  {
	nodes =
	  {
		a = 2,
		b = 1.5,
		c = 3,
		d = 2
	  },
	connections =
	  {
		{
		  s = "a",
		  e = "b",
		  t = 5
		},
		{
		  s = "b",
		  e = "c",
		  t = 4
		},
		{
		  s = "c",
		  e = "d",
		  t = 4
		},
		{
		  s = "a",
		  e = "c",
		  t = 7
		}
	  }
  }

s = Start,
e = End,
Start and end are interchangable, it's 2-way traffic.
t = travel time

Of cource the map is more complex (more nodes, more connections). How could I make a pathfinding algorithm that finds the fastest route between 2 given nodes?

If needed I could completely change the structure of the map table.

From the little I know about pathfinding you need to look at A*, bi-directional BFS or Dijkstra. I think bi-directional BFS is the best/easiest though.

Edit: I've seen Jumper recommended a lot, you won't want to be using it all but it gives you a starting point to work from.

Look there's lots of ways you could do pathfinding; I could probably list a dozen or so off the top of my head, but at the end of the day, with the way your graph and nodes are setup, one of the best-first searches will give you the best result. I'd probably suggest A* as it will give you the best path every time at a low(ish) computational cost. However if you don't mind the AI not always finding the optimal path then something like a Greedy Best-first search would be significantly lower on computational cost, as it simply follows the nodes that are the cheapest, which obviously sometimes taking the slightly more expensive node is better as nodes after it may be cheaper, or just a shorter path.

I don't care too much about computing time, I'm not going to have more then 15 nodes anyway.

Which of those algorithms is the easiest to code?

Greedy best-first search would be easiest. Start at your root, look at the nodes, and pick the cheapest node, and as long as you're not going backwards you're good.

Do you always get the best path that way? What if the nodes behind the first (cheap) node are very expensive? Or do you mean calculating all possible (non-repeating) paths from the starting point?

Oops sorry that was meant to say Greedy Best-first search :P/> and no you don't always get the best path doing that as it only takes the next node into account, instead of looking ahead. Maybe A* would be better for you to do, given your requirements.

I found this:
https://github.com/lattejed/a-star-lua/blob/master/a-star.lua
I'm going to try editing that to fit my needs, shouldn't be too hard.

Check out my pathfinding algorithm based on A*: https://github.com/Akuukis/TurtleColorWars/blob/master/Nav.lua
Add it to your code, and do

Nav.UpdateMap({0,0,0},false) -- only once when starting the code
Nav.Go({x,z,y,f}) -- x is currently facing dir (the map initiates like that), and optional f is facing dir from 1 to 4 clockwise. 

you can save your waypoints as waypoint1={x=123, z=231, y=312, f=2} and then do Nav.Go(waypoint1)

Isn't your code meant for navigating turtles? I'm looking for a way to pathfind between nodes, supplied by a map. I explained everything in the first post.

Thanks anyway.

flaghacker, on 24 July 2014 - 07:14 PM said:

Isn't your code meant for navigating turtles? I'm looking for a way to pathfind between nodes, supplied by a map. I explained everything in the first post.

Thanks anyway.

Originally yes, but it will do for you also. Set the position of turle by manually changing values of Nav.Pos table, then supply the map by doing a lot of Nav.UpdateMap({x,z,y},isBlocked) calls, and Nav.GetPath({targetX,targetZ,targetY}) will return you a table with numbers from 1-6 (where 1 means go North, 2 - East, 3 - South, 4 - West, 5 - Up, 6 - Down) in correct order to get to target destination. Or if you need table with coordinates, then you need to edit line 470 from "return fpath" into "return path".

Oops, checked the spoiler part again and understood that you are not talking about Minecraft world but about theoretical points. It's a way different code then, maybe check out this useful stuff that helped me a lot:
http://www.raywender...o-a-pathfinding
http://theory.stanfo...ameProgramming/
and http://qiao.github.io/PathFinding.js/visual/

Good luck!