Optimal Path Algorithm of the small game in practice
Preface
Recently, I had to make a small game about the shortest connecting line of a number of points, and realized how unsound my knowledge about algorithms is == Learning from my mistakes, growing wiser. I’ll summarize it briefly in this article. If there is a god who has no intention to see this article, please pat.
Demand
Given a random number of points, find the shortest line connecting those points. This can be extended with a mini-game where a number of points are given and the user draws lines on a panel to connect the points, determines if it is the shortest path, and gives a hint. In essence, it is entitled to a shortest path algorithm in an undirected complete graph with no particular source points.
Dijkstra’s and Floyd’s algorithms
Searching for information, Dijkstra’s algorithm and Floyd’s algorithm are the algorithms that are closer to the requirements.
stra algorithm
Dijkstra’s algorithm is a typical single-source shortest path algorithm for computing the shortest path from one node to all other nodes. The main feature is to expand outward in layers centered on the start point until it expands to the end point. Algorithm idea:
- Initially, S contains only source points, i.e., S = {v}, and the distance of v is 0. U contains vertices other than v, i.e., U = {rest of vertices}, and <k,v> is normally weighted if v has an edge with vertex k in U. If k is not an outgoing neighbor of v, <k,v> is weighted at ∞.
- Select a vertex k from U with minimum distance from v and add k, to S.
- Modify the distance of each vertex in U, using k as the newly considered intermediate point; if the distance from the source point v to the vertex u (passing through the vertex k) is shorter than the original distance (not passing through the vertex k), modify the value of the distance to the vertex u. The modified value of the distance to the vertex k is the distance of the vertex k plus the weights on the edges.
- Repeat steps 2 and 3 until all vertices are included in S.
Floyd’s algorithm
Floyd-Warshall algorithm (Floyd-Warshall algorithm) is an algorithm for solving the shortest path between any two points, which can correctly deal with directed graphs or the shortest path problem with negative weights. Algorithm idea:
- Start with any one-sided path. The distance between all two points is the weight of the edge, or infinity if no edges are connected between the two points.
- For each pair of vertices u and v, see if there exists a vertex k such that the path from u to k to v is shorter than the known path. If so update it.
For details on Dijkstra’s algorithm and Floyd’s algorithm see Shortest Path - Dijkstra’s algorithm and Floyd’s algorithm
Specific implementations
Borrowing ideas from Dijkstra’s algorithm and Floyd’s algorithm and combining them with the requirements, the implementation is started.
Ideas for implementation
- Randomly generate a number of points, each point has three attributes: x-coordinate, y-coordinate, and whether or not it has been visited.
- use the collinear theorem to calculate the straight line distance between any two points to generate a two-dimensional matrix
- Denote the source point as uNext, select a shortest line with uNext from all the lines, put this point on the line (re-denoted as uNext) into U, and put the shortest line into an array.
- Repeat step 3 until all points have been placed into U. Calculate the sum of the paths in the array and return the shortest path.
- iterate through the points to find the shortest path when each point is used as a source, compare, and arrive at the final shortest path.
Main code
Declare class Graph and its properties and methods. Implement random point generation. Make some restrictions so that the points don’t get too clustered.
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
function Graph(v,w) {
this.vertices = v;
this.points = []; // V 总的点集
this.u = []; // U 点集
this.width = w;
this.pythagorean = pythagorean; // 勾股定理
this.getPoints = getPoints;
this.matrix = [];
this.getMatrix = getMatrix;
this.path = [];
this.pathSum = 0;
this.getPath = getPath;
this.getTempPath = getTempPath;
}
function Point(x, y) {
this.x = x;
this.y = y;
this.visited = false;
}
function getPoints() {
this.points = [];
for (var i = 0; i < this.vertices; i++) {
this.points[i] = new Point(Math.ceil(15+Math.random()*(this.width-30)),Math.ceil(15+Math.random()*(this.width-30)));
}
for (var j = 0; j < this.vertices; j++) {
for(var k = j+1; k < this.vertices; k++) {
if(Math.abs(this.points[j].x - this.points[k].x) < 30 && Math.abs(this.points[j].y - this.points[k].y) < 30) {
this.getPoints();
}
}
}
}
Calculate the straight-line distance between any two points using the collinear theorem to generate a two-dimensional matrix.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// a^2 + b^2 = c^2
function pythagorean(a, b) {
return Math.pow(this.points[a].x-this.points[b].x,2) + Math.pow(this.points[a].y-this.points[b].y,2);
}
function getMatrix() {
var min = 999999;
var pointI, pointJ;
for (var i = 0; i < this.vertices; i++) {
this.matrix[i] = [];
for (var j = 0; j < this.vertices; j++) {
if (i === j) {
this.matrix[i][j] = 0;
} else {
this.matrix[i][j] = this.pythagorean(i,j);
}
}
}
return this.matrix;
}
Notate the source point as uNext, select a shortest line from all the lines to uNext, put this point on the line (re-notated as uNext) into U, and put the shortest line into an array. Repeat this step until all points have been put into U. Calculate the sum of the paths in the array and return the shortest path.
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
function getTempPath(uNext) {
this.path = [];
this.u = [];
var pathTempSum = 0;
for (var k = 0; k < this.vertices; k++) {
this.points[k].visited = false;
}
this.u.push(uNext);
this.points[uNext].visited = true;
while (this.u.length !== this.vertices) {
var min = 999999;
var tempNext;
for (var i = 0; i < this.vertices; i++){
if(this.points[i].visited === false) {
if(this.matrix[uNext][i] < min) {
min = this.matrix[uNext][i];
tempNext = i;
}
}
}
uNext = tempNext;
this.u.push(uNext);
this.path.push(min);
this.points[uNext].visited = true;
}
for (var j = 0; j < this.path.length; j++) {
pathTempSum += this.path[j];
}
return pathTempSum;
}
Iterate through the points, find the shortest path when each point is used as a source, compare, and come up with the final shortest path.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function getPath() {
var min = 9999999;
var temp = 0;
var shortest;
for(var i = 0; i < this.vertices; i++) {
temp = this.getTempPath(i);
if(temp < min) {
min = temp;
shortest = i;
}
}
this.pathSum = min;
this.getTempPath(shortest);
}
Make mini-games with canvas
Main idea:
- new a Graph object. Draw randomly generated points using canvas.
- Listen to the touchstart, touchmove, touchend events. The touchmove event determines whether a point in the graph is passed and records it in an array; the touchend event triggers a change in the style of the passed point, and the points are connected by a straight line. 3.
- Click to start detection, calculate the path passed, and compare the passed path and the shortest path, and give a hint respectively.
Demo address: https://119.29.142.213/shortest
6 Inadequate
- UI aspects to be realized: breathing light effect when passing points; canvas edges can not draw lines, etc.; show restart button after error
- Declared more arrays and used more loops. I’ll think about it ==b