Ponderate dijkstra relative to previous position

I use dijkstra in my rust game to find path to a destination. My game is in a square grid like this:

There is, for illustration, the Rust code which use dijkstra:

use crate::map::Map;
use crate::physics::GridPoint;
use pathfinding::prelude::dijkstra;

pub fn find_path(map: &Map, from: &GridPoint, to: &GridPoint) -> Option<Vec<GridPoint>> {
match dijkstra(from, |p| map.successors(p), |p| *p == *to) {
None => None,
Some(path) => Some(path.0),
}
}

// ...

pub fn successors(&self, from: &GridPoint) -> Vec<(GridPoint, i32)> {
let mut successors = vec![];

for (mod_x, mod_y) in [
(-1, -1),
(0, -1),
(1, -1),
(-1, 0),
(0, 0),
(1, 0),
(-1, 1),
(0, 1),
(1, 1),
]
.iter()
{
let new_x = from.x + mod_x;
let new_y = from.y + mod_y;

if new_x < 0 || new_y < 0 {
continue;
}

if let Some(next_tile) = self.terrain.tiles.get(&(new_x as u32, new_y as u32)) {
successors.push((GridPoint::new(new_x, new_y), next_tile.pedestrian_cost))
}
}

successors
}
// ...



And visualization of found path (white is found path, pink is goal):

The found path is not a direct line. I'm not surprised, because the weight of diagonal is the same as lateral. With what I understand with dijkstra is I can return successor with weight for a coordinate. But I can't increase weight of diagonal/lateral according to previous position (ex: comming from West -> moving to Est will be less weight; maybe it is not the solution ...).

How can I achieve that ? With another algorithm than dijkstra ?

• The weight represents the distance between the nodes, so since the distance for horizontal and diagonal are not the same, they should not have the same weight Commented May 18, 2021 at 15:15
• Good point ! Thanks
– bux
Commented May 18, 2021 at 15:28

Once I created this algorithm. You need to increase weight in diagonal paths: you will use the value 10 for non diagonal, and value 14 for diagonal. This value is the distance between squares; 10 is the width and height of square, 14 is the distance between center points of diagonal squares.

This is the code that I calculated the distance between two pathCell:

int distanceBetween(PathCell A, PathCell B) //find path a to b
{
int sum;

//Diagonal cost and not diagonal cost
int diagonalCost = 14;
int notDiagonalCost = 10;

//visitedPaths
int ndiagonal=0;
int nNotDiagonal=0;

//position now
int nowX, nowY;

//object pos
float posBX = B.pos.x;
float posBY = B.pos.y;

//setting new pos
nowX = A.pos.x;
nowY = A.pos.y;

//calculating the path distance
while(nowX != posBX && nowY != posBY)
{
int difX = posBX - nowX;
int difY = posBY - nowY;

//std::cout << nowX << ", " << nowY << " | " << posBX << ", " << posBY << std::endl;

if (difX != 0 || difY != 0)
{
if(difX != 0 && difY != 0)
{
ndiagonal++;
}
else
{
nNotDiagonal++;
}

int aX = abs(difX);
int aY = abs(difY);
nowX += (difX/aX);
nowY += (difY/aY);
}
}

int difX = abs(posBX - nowX);
int difY = abs(posBY - nowY);
nNotDiagonal += difX + difY;

sum = (ndiagonal * diagonalCost) + (nNotDiagonal * notDiagonalCost);

return fabs(sum);
}


You can see the full project code here.

• Thanks ! That's an interesting idea. Note i maybe found another solution by using A* and determine heuristic with distance from goal.
– bux
Commented May 18, 2021 at 11:31
• ur welcome, good! This A* heuristic save a lot of memory and is fastly, you can use this (from github repository): pathCellVector[newPathCellIndex]->parent = theNode; pathCellVector[newPathCellIndex]->G = theNode->G + distanceBetween(*pathCellVector.at(newPathCellIndex), *theNode); pathCellVector[newPathCellIndex]->H = distNowToB; pathCellVector[newPathCellIndex]->somaPeso(); Commented May 19, 2021 at 1:35