Full code:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
<style type="text/css">
#box1 table{
border: 0px;
border-collapse: collapse;
cursor: pointer;
background-color: gray;
}
#box1 th {
border: 0px;
border-collapse: collapse;
cursor: pointer;
}
#box1 td{
border: 1px solid #000;
border-collapse: collapse;
cursor: pointer;
text-align: center;
font-size: 4;
}
#box1{
border: 0px;
}
.wall{
background-color: black;
}
.startPoint{
background-color: blue;
}
.targetPoint{
background-color: blue;
}
.passed{
background-color: yellow;
}
</style>
</head>
<body>
Click on the gray grid to set it as a barrier (black), click on the barrier to clear it
<div id="box1"></div>
<button onclick="startSearch()">Start pathfinding</button>
<button onclick="initRingWalls()">Generate ring barrier</button>
<button onclick="initPointWalls()">Generate point obstacles</button>
</body>
<script type="text/javascript">
var map_code_td = new Map();
var row_count = 40;
var col_count = 40;
var rowNum_start = 1;
var colNum_start = 1;
var rowNum_target = 20;
var colNum_target = 20;
var map_code_wallYn = new Map();
var code_start = rowNum_start + "_" + colNum_start;
var code_target = rowNum_target + "_" + colNum_target;
// The auxiliary help displays a background chessboard with horizontal and vertical stripes, without any events or business logic.
function initBox1( ) {
var table = document.createElement("table");
table.rules = 'all' ;
for (var rowNum = 1; rowNum <= row_count; rowNum + + ) {
var tr = document.createElement("tr");
for (var colNum = 1; colNum <= col_count; colNum + + ) {
var td = document.createElement("td");
td.width = 10;
td.height = 10;
td.className="road";
tr.appendChild(td);
var code = rowNum + "_" + colNum;
map_code_td.set(code, td);
}
table.appendChild(tr);
}
document.getElementById( "box1" ).appendChild(table);
table.addEventListener( "click", setOrClearWall );
var code_start = rowNum_start + "_" + colNum_start;
var code_target = rowNum_target + "_" + colNum_target;
map_code_td.get( code_start ).className = "startPoint";
map_code_td.get( code_target ).className = "targetPoint";
}
function initPointWalls(){
// clear obstacles
clearAllWalls();
for (var rowNum = 1; rowNum <= row_count; rowNum + + ) {
for (var colNum = 1; colNum <= col_count; colNum + + ) {
var code = rowNum + "_" + colNum;
if( code == code_start || code == code_target ){
continue;
}
// Right 1/3 chance of becoming an obstacle
var randomNum = randomBetween(1,10000);
if(randomNum < 3333){
var td = map_code_td.get(code);
td.className = "wall";
map_code_wallYn.set( code, 'y' );
}
}
}
}
// Mouse click event listening method, used to set the clicked grid as a wall
function setOrClearWall(){
var td = event.srcElement;
var rowNum = td.parentElement.rowIndex + 1;
var colNum = td.cellIndex + 1;
var code = rowNum + "_" + colNum;
if( td.className == "wall" ){
td.className = "road";
map_code_wallYn.set( code, "n" );
}else if( td.className =='road' ){
td.className = "wall";
map_code_wallYn.set( code, "y" );
}
}
function randomBetween(minNum,maxNum){
return Math.floor(Math.random() * (maxNum - minNum + 1)) + minNum;
}
function clearAllWalls(){
for (var rowNum = 1; rowNum <= row_count; rowNum + + ) {
for (var colNum = 1; colNum <= col_count; colNum + + ) {
var code = rowNum + "_" + colNum;
if( code == code_start || code == code_target){
continue;
}
var wallYn = map_code_wallYn.get(code);
if( wallYn == 'y' ){
map_code_td.get( code ).className = "";
map_code_wallYn.set( code, "n" );
}else{
var td = map_code_td.get(code);
if( td.className == 'passed' ){
td.className = "";
}
}
}
}
}
function initRingWalls(){
// clear obstacles
clearAllWalls();
//Set the third row as a barrier
var circles = [2,4,6,8,10,12,14,16,18];
for(var i in circles){
var circle = circles[i];
var randomNum = randomBetween(1,4);
var randomNum_1 = randomBetween(circle,col_count - circle);
var randomNum_2 = randomBetween(circle,col_count - circle);
var randomNum_3 = randomBetween(circle,row_count - circle);
var randomNum_4 = randomBetween(circle,row_count - circle);
// top row
for (var colNum = circle; colNum <= ( col_count - circle );colNum + + ){
if(randomNum == 1){
if(colNum == randomNum_1){
continue;
}
}
var code = circle + "_" + colNum;
map_code_td.get( code ).className = "wall";
map_code_wallYn.set( code, "y" );
}
// bottom row
for (var colNum = circle; colNum <= ( col_count - circle );colNum + + ){
if(randomNum == 2){
if(colNum == randomNum_2){
continue;
}
}
var code = ( row_count - circle ) + "_" + colNum;
map_code_td.get( code ).className = "wall";
map_code_wallYn.set( code, "y" );
}
// left column
for (var rowNum = circle; rowNum <= ( row_count - circle ); rowNum + + ){
if(randomNum == 3){
if( rowNum == randomNum_3 ){
continue;
}
}
var code = rowNum + "_" + circle;
map_code_td.get( code ).className = "wall";
map_code_wallYn.set( code, "y" );
}
// right column
for (var rowNum = circle; rowNum <= ( row_count - circle ); rowNum + + ){
if(randomNum == 4){
if( rowNum == randomNum_4 ){
continue;
}
}
var code = rowNum + "_" + ( col_count - circle );
map_code_td.get( code ).className = "wall";
map_code_wallYn.set( code, "y" );
}
}
}
// Check whether the grid represented by code is passable
function canPass( code ){
var arr = code.split("_");
var rowNum = parseInt( arr[0])
var colNum = parseInt( arr[1] );
if( rowNum > row_count || rowNum < 1 || colNum > col_count || colNum < 1 ){
// This position has exceeded the boundary and cannot be moved
return false;
}
var wallYn = map_code_wallYn.get(code);
if( wallYn == 'y' ){
// This location is a wall and cannot be walked
return false;
}
return true;
}
initBox1( );
function startSearch( ){
// todo initialization graph
var graph = initGraph();
var { distances, previous } = dijkstra(graph, code_start);
var path = getPath( previous );
printPath( path );
}
function printPath( path ){
console.log( path );
if( !path ){
return;
}
for (var i = 0; i < path.length; i + + ) {
var code = path[i];
if( code == code_start || code == code_target ){
continue;
}
var wallYn = map_code_wallYn.get(code);
if( wallYn == 'y' ){
// In case the path generated by the algorithm contains a wall
continue;
}
var td = map_code_td.get(code);
td.className = "passed";
}
}
//Scan n*m grid and generate graph structure
function initGraph(){
var graph = {};
for( var rowNum = 1; rowNum <= row_count; rowNum + + ){
for( var colNum = 1; colNum <= col_count; colNum + + ){
var code = rowNum + "_" + colNum;
//Each code can go to its upper, lower, left, and right grids, but it needs to exclude grids that cross boundaries and obstacles.
var code_right = rowNum + "_" + ( colNum + 1 );
var code_left = rowNum + "_" + ( colNum - 1 );
var code_up = (rowNum - 1) + "_" + colNum;
var code_down = (rowNum + 1) + "_" + colNum;
var map_reachable = {};
if( canPass( code_right ) ){
map_reachable[code_right] = 1;
}
if( canPass( code_left ) ){
map_reachable[code_left] = 1;
}
if( canPass( code_up ) ){
map_reachable[code_up] = 1;
}
if( canPass( code_down ) ){
map_reachable[code_down] = 1;
}
graph[code] = map_reachable;
}
}
return graph;
}
// The specific implementation of Dijkstra's algorithm is unclear (I struggled to deduce it when I was learning data structures and algorithms, but I don't know it now). We only use it as a black box.
function dijkstra(graph, start) {
const distances = {};
const visited = {};
const previous = {};
const queue = [];
for (let vertex in graph) {
distances[vertex] = Infinity;
previous[vertex] = null;
queue.push(vertex);
}
distances[start] = 0;
while (queue.length) {
let current = null;
for (let vertex of queue) {
if (!current || distances[vertex] < distances[current]) {
current = vertex;
}
}
queue.splice(queue.indexOf(current), 1);
visited[current] = true;
for (let neighbor in graph[current]) {
let distance = graph[current][neighbor];
let totalDistance = distances[current] + distance;
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
previous[neighbor] = current;
}
}
}
return { distances, previous };
}
function getKeyByValueInPrevious( previous,value ){
for(var key in previous){
if( previous[key] == value ){
return key;
}
}
return null;
}
// Get the shortest path from the starting point to the end point from the predecessor node map
function getPath( previous ){
console.log(previous)
// Determine whether the previous key contains code_target
if( previous[ code_target ] ){
console.log( "previous key contains " + code_target );
}else{
console.log( "previous key does not contain " + code_target );
alert("There is no path between the starting point " + code_start + " and the end point " + code_target + "");
return null;
}
var path=[];
var target = code_target;
var loopTime = 0;
var maxLoopCount = row_count * col_count;
while( true ){
loopTime + + ;
if( loopTime > maxLoopCount ){
break;
}
if( target != undefined ){
path.push( target );
}
var prev = previous[target];
if( prev == code_start ){
path.push( code_start );
break;
}
target = prev;
}
path = path.reverse();
return path;
}
</script>
</html>
The first parameter graph of dijkstra's algorithm is a graph structure, such as the following picture:
The distance from point “0” to point “1” is 6, the distance from point “1” to point “2” is 5,…
Transformed into a graph structure, it is:
{
"0": {
"1": 6, // means the distance from point "0" to point "1" is 6
"3": 2 //Indicates that the distance from point "0" to point "3" is 2
},
"1": {
"2":5, // represents the distance from point "1" to point "2" wired 5
"5":3 //Indicates that the distance from point "1" to point "5" is 3
},
"2": { }, // Empty means point "2" cannot reach any other point
"3": {
"1":7,
"4":5
},
"4": {
"5":5,
"6":1
},
"5": { },
"6": { }
}
But our graph is an m*n grid as follows:
How to convert it into the required graph json structure?
We take a code for each of the n*m grids, the format is: “${rowNum}_${colNum}”,
Traverse each grid. For each grid, there can be up to 4 other reachable grids (grids beyond the boundary and grids with obstacles need to be excluded), so the program can be scanned once to generate it. The initGraph method in the code That is, it is used to initialize the graph.
The following is the approximate structure of the graph generated by scanning n*m grids using the initGraph method:
Click “Start” to generate the shortest path using Dijkstra’s algorithm:
The gray grid indicates that you can walk, and the distance is 1. The black grid represents the wall, which cannot be walked. The distance is not reflected in the graph structure and is equivalent to infinity. Of course, we can also set different colors or background images for the grid. For example, if it is set to water, the distance is 10, it means it is slightly difficult to walk; if it is set to mountain, the distance is 50, it means it is difficult to walk; if it is set to a monster, the distance is 500 , which means it is very difficult to walk; of course we can also set it as a mine. When you are an ordinary user, the distance is 10000, which means it is not easy to walk. If you purchased flying equipment, the distance is 1. From this point of view, the distance in the game The pathfinding algorithm is not very difficult. Of course, if you use Dijkstra’s algorithm directly, yes
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57208 people are learning the system