Forum

CS2D

Scripts

Doubt with A* Pathfinding

Forums overview CS2D overview Scripts overview Log in to reply

Doubt with A* Pathfinding

6 replies

Doubt with A* Pathfinding

Starkkz
Moderator Off

Offline

06.07.11 10:45:14 pm

Finally I made it work, but it's not fully working. I mean, my problem is that it search the path and doesn't return a shorter path.

Spoiler

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

function table.empty(tab)
	for k, v in pairs(tab) do
		return false
	end
	return true
end

function FindPath(Map,fx,fy,tx,ty)
	local Node = {}
	local sizex = #Map
	local sizey = #Map[1]
	local curbase = {x = fx,y = fy}
	
	local function Euclidean(fx,fy,tx,ty)
		return math.sqrt((fx-tx)^2 + (fy-ty)^2)
	end
	
	local function Manhattan(fx,fy,tx,ty)
		return math.abs(fx-tx) + math.abs(fy-ty)
	end
	
	-- To get the openlist
	local function openlist()
		local open = {}
		for x = 0, sizex do
			for y = 0, sizey do
				if Node[x][y].Open then
					table.insert(open,{x = x,y = y})
				end
			end
		end
		return open
	end
	
	-- To get the closedlist
	local function closedlist()
		local closed = {}
		for x = 0, sizex do
			for y = 0, sizey do
				if Node[x][y].Closed then
					table.insert(closed,{x = x,y = y})
				end
			end
		end
		return closed
	end
	
	-- Configurate Nodes
	for x = 0, sizex do
		Node[x] = {}
		for y = 0, sizey do
			NodeInfo = {
				Open = false,
				Closed = false,
				G = 0,
				H = Euclidean(x,y,tx,ty),
				parent = {}
			}
			function NodeInfo.F()
				return NodeInfo.G + NodeInfo.H
			end
			Node[x][y] = NodeInfo
		end
	end
	Node[fx][fy].Open = true
	
	local function FixedPath()
		local i = {x = tx,y = ty}
		local path = {}
		while Node[i.x][i.y].parent.x and Node[i.x][i.y].parent.y do
			local Details = {
				x = i.x,
				y = i.y,
				F = Node[i.x][i.y].F(),
				G = Node[i.x][i.y].G,
				H = Node[i.x][i.y].H
			}
			table.insert(path,Details)
			i = Node[i.x][i.y].parent
		end
		return path
	end
	
	while not table.empty(openlist()) do
		local lF = nil -- Lowest F node
		for k, v in pairs(openlist()) do
			if not lF or Node[v.x][v.y].F() < Node[lF.x][lF.y].F() then
				lF = v
				msg("F: "..Node[v.x][v.y].F().." - "..v.x.." "..v.y)
			end
		end
		msg("Lowest F: "..Node[lF.x][lF.y].F().." - "..lF.x.." "..lF.y)
		Node[lF.x][lF.y].Closed = true
		Node[lF.x][lF.y].Open = false
		curbase = lF
		
		if curbase.x == tx and curbase.y == ty then
			return FixedPath()
		end
		
		local NearNodes = {}
		local function AddNode(x,y)
			if not Node[x][y].Closed and Map[x][y] == 0 then
				table.insert(NearNodes,{x = x,y = y})
			end
		end
		AddNode(curbase.x,curbase.y+1); AddNode(curbase.x+1,curbase.y)
		AddNode(curbase.x,curbase.y-1); AddNode(curbase.x-1,curbase.y)
		for k, v in pairs(NearNodes) do
			local score = Node[curbase.x][curbase.y].G + Euclidean(curbase.x,curbase.y,v.x,v.y)
			if not Node[v.x][v.y].Open then
				Node[v.x][v.y].Open = true
				Node[v.x][v.y].parent = curbase
				Node[v.x][v.y].G = score
				msg("Added Element: "..v.x.." "..v.y.." "..Node[v.x][v.y].F())
			elseif score < Node[v.x][v.y].G then
				Node[v.x][v.y].parent = curbase
				Node[v.x][v.y].G = score
				msg("Added Element: "..v.x.." "..v.y.." "..Node[v.x][v.y].F())
			end
		end
	end
	return nil, "Couldn't find the path"
end

I tested it using this other part.

Spoiler

Try to use it in de_dust, with the coords:

X: 37 Y: 4

X: 37 Y: 6

It will give you a wrong path, anyways its a walkable path.

My Opinion: I think at the part you search a low G cost, I made something wrong.

Re: Doubt with A* Pathfinding

EnderCrypt
User Off

Offline

06.07.11 10:48:52 pm

a* path finding finds the fastest way automatically, due the Technic, se this

IMG:https://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif

edit: heres the Weighted A* path finding

IMG:https://upload.wikimedia.org/wikipedia/commons/8/85/Weighted_A_star_with_eps_5.gif

Re: Doubt with A* Pathfinding

Starkkz
Moderator Off

Offline

06.07.11 10:52:57 pm

That's why i prefer A*, it works very well. But it gives a larger path. Or you mean it gives a fast path, but larger?

Re: Doubt with A* Pathfinding

EnderCrypt
User Off

Offline

06.07.11 10:55:28 pm

hm i already made a path finding script, i prefer weighted a star... its very hard... i wish you luck

http://en.wikipedia.org/wiki/A*_search_algorithm

Re: Doubt with A* Pathfinding

Starkkz
Moderator Off

Offline

07.07.11 12:45:38 am

Hmm, watching it better. The F cost always gives the same, I should try with H because that's the cost from the current node to the last node. And about that, the other nodes can be found with G cost, the F cost is not necessary.

Re: Doubt with A* Pathfinding

Lee
Moderator Off

Offline

07.07.11 02:13:33 am

Adapted from http://en.wikipedia.org/wiki/A-star_algorithm

Sample run (overloading CS2D's native functions)
http://codepad.org/TaoK5hdk

function table.find(t, x)
	for _,v in ipairs(t) do if x == v then return _ end end
end

function pqueue(initial, cmp)
	cmp = cmp or function(a,b) return a<b end
	return setmetatable({unpack(initial or {})}, {
		__index = {
			push = function(self, v)
				table.insert(self, v)
				local next = #self
				local prev = math.floor(next/2)
				while next > 1 and self[next] < self[prev] do
					-- swap up
					self[next], self[prev] = self[prev], self[next]
					next = prev
					prev = math.floor(next/2)
				end
				self[next] = v
				self.size = self.size + 1
			end,
			size = 0,
			pop = function(self)
				if #self < 2 then
					return table.remove(self)
				end
				local r = self[1]
				self[1] = table.remove(self)
				local root = 1
				if #self > 1 then
					local size = #self
					local v = self[root]
					while root < size do
						local child = 2*root
						if child < size then
							if child+1 < size and self[child+1] < self[child] then child = child + 1 end
							if cmp(self[child], self[root]) then
								-- swap down
								self[root], self[child] = self[child], self[root]
								root = child
							else
								self[root] = v
								break
							end
						else
							self[root] = v
							break
						end
					end
				end
				self.size = self.size - 1
				return r
			end}})
end


local xsize = map("xsize")
local ysize = map("ysize")

local function dist(point, goal)
	-- simple euclidean distance as our heuristic function
	return (goal%xsize - point%xsize)^2 + (math.floor(goal/xsize - point/xsize))^2
end

local function h()
	-- dist takes care of everything, weigh everything else with equal favorability
	return 0
end

local function neighbors(next)
	-- return a list of neighboring tiles
	local near = {}
	if next/xsize >= 1 then
		table.insert(near, next-xsize)
	elseif next/xsize < ysize then
		table.insert(near, next+xsize)
	end
	if next%xsize > 0 then
		table.insert(near, next-1)
	elseif next%xsize < xsize then
		table.insert(near, next+1)
	end
	return ipairs(near)
end

-- our graph is the strongly connected rectangular mesh
-- nodes/vertices are numbers hashed as numbers with y*xsize+x
function search(start, goal)
	local this = start
	local g_, h_, f_
	local visited, graph, path = {}, pqueue({}, function(a, b)
		return g_[a]+h(a, goal) < g_[b]+h(b, goal)
	end), {}

	graph:push(start)

	-- setup our heuristic memcache
	g_, h_, f_ =
		{[start] = 0},
		{[start] = h(start, goal)},
		{[start] = h(start, goal)}

	while graph.size > 0 do
		this = graph:pop()

		-- end condition
		if this == goal then
			-- need to backtrace from goal to start in path
			function backtrace(this)
				if path[this] then
					local p = backtrace(path[this])
					table.insert(p, this)
					return p
				else
					return {this}
				end
			end
			return backtrace(this)
		end

		visited[this] = true
		for _,next in neighbors(this) do

			if not visited[next] and
				tile(next%xsize, math.floor(next/xsize), "walkable") then

				local gscore = g_[this] + dist(this, next)
				local advance
				if not table.find(graph, next) then
					graph:push(next)
					advance = true
				elseif gscore < g_[next] then
					advance = true
				else
					advance = false
				end

				if advance then
					path[next] = this

					-- f'(x) = g(x) + h'(x)
					g_[next] = gscore
					h_[next] = h(next, goal)
					f_[next] = g_[next] + h_[next]
				end
			end
		end
	end

end

Technically, we shouldn't use euclidean distance function as our heuristic as we're limiting the neighbor finding function to only hrz/vrt adjacent tiles. To get the correct estimated distance, don't square the components.

We also use a heap structure to keep track of our path, this gives us nlog(n) time complexity on the search algorithm rather than n^2.

Tentatively, we treat the map as a vertex matrix, but for efficiency's sake, namely that tables are expensive, we hash each vertex node as a single integer unique for each x and y. The most simple/straightforward bijection from N^2 to N in this case is hash(x,y) = y*xsize+x (for countably infinite sets, this can be proven via Cantor's diagonalizing argument, for finite sets, the proof is trivial). So to search for a path between (start.x, start.y) and (end.x, end.y), you would need to hash both before passing them into the function.

1
2
3
4

function point_hash(x,y)
	return x+y*map("xsize")
end
search(point_hash(startx, starty), point_hash(endx, endy))

The current heuristic assumes that all tiles are equally favorable, and hence only weighs based on distance. This in turn defeats the main advantages of A* or kruskal type derivative algorithms in that they can use any arbitrary massing function. If you do not care whether a gatefield is better than a longer route, then for efficiency's sake, you should look into Djkstra's algorithm for unweighted graphs. If not, you may need to change the h function accordingly.

Re: Doubt with A* Pathfinding

Starkkz
Moderator Off

Offline

07.07.11 02:28:07 am

Huh thanks for the explaination and the demonstration of the script, I'm not sure because I don't know but I think that the fastest pathfinding algorithm is A*, anyways I'll search for the Dijkstra. If I can find better methods than the currently used.
Thank you so much.