PathFinding-Visual/AStarSearch.js at master · Quickz/PathFinding-Visual · GitHub

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

const AStarSearch = {

	/*
	 * - - - Algorithm - - -
	*/
	run: function(source, target, grid)
	{
		// saving grid so the methods can access it
		this.grid = grid;

		var start = new Node(source.x, source.y, source, target);
		start.gCost = 0;
		start.hCost = target.x + target.y - start.gridX - start.gridY - 1;

		// discovered nodes to be evaluated
		var open = [];

		// set of nodes already evaluated
		var closed = [];

		// will contain every single node
		// in a correct order to retrace
		// it's discovery path
		var visited = [];

		open.push(start);
		visited.push(start);

		var current;
		while (true)
		{
			// finding lowest f cost
			current = this.lowestCost(open);
			// removing current from open list
			open.splice(this.findIndex(open, current), 1)[0];
			// adding current to closed list
			closed.push(current);

			// path found
			if (current.gridX == target.x &&
				current.gridY == target.y)
			{
				return {
					"path": current,
					"visited": visited
				};
			}

			// obtaining neighbors
			current.neighbours = this.getNeighbours(
				current.gridX, current.gridY, source, target);

			// looping through neighbours
			var lng = current.neighbours.length;
			for (let i = 0; i < lng; i++)
			{
				let currNode = current.neighbours[i];

				// checking if it's in closed list
				if (this.findIndex(closed, currNode) >= 0)
					continue;

				// if shorter path found
				var existing = this.findIndex(open, currNode);
				if (existing >= 0 &&
					open[existing].parent.fCost >= current.fCost &&
					open[existing].parent.gCost > current.gCost)
				{

					// removing old (bad) node
					open.splice(existing, 1);

				}

				// not in open
				if (this.findIndex(open, currNode) < 0)
				{
					currNode.parent = current;

					// adding neighbour to open nodes
					open.push(currNode);

					// adding neighbour to visited nodes
					if (this.findIndex(visited, currNode) < 0)
						visited.push(currNode);

				}
			}

			// no path found
			if (open.length == 0)
			{
				console.log("path not found");
				return;
			}

		}
	},

	/*
	 * - - - Methods - - -
	*/

	lowestCost: function(nodes)
	{
		var lowest = nodes[0];
		for (let i = 1; i < nodes.length; i++)
		{
			if (nodes[i].fCost <= lowest.fCost &&
				nodes[i].hCost < lowest.hCost)
				lowest = nodes[i];
		}
		return lowest;
	},

	findIndex: function(nodes, node)
	{
		for (var i = 0; i < nodes.length; i++)
		{
			if (nodes[i].gridX == node.gridX &&
				nodes[i].gridY == node.gridY)
				return i;
		}
		return -1;
	},

	validCoord: function(x, y)
	{
			   // inside bounds
		return x >= 0 && x < this.grid.length &&
			   y >= 0 && y < this.grid.length &&
			   // walkable
			   this.grid[x][y] != 2;
	},

	getNeighbours: function(x, y, source, target)
	{
		var neighbours = [];
		// top
		if (this.validCoord(x, y - 1))
			neighbours.push(new Node(x, y - 1, source, target));
		// right
		if (this.validCoord(x + 1, y))
			neighbours.push(new Node(x + 1, y, source, target));
		// bottom
		if (this.validCoord(x, y + 1))
			neighbours.push(new Node(x, y + 1, source, target));
		// left
		if (this.validCoord(x - 1, y))
			neighbours.push(new Node(x - 1, y, source, target));

		return neighbours;
	}

};