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 – BlueRaja - Danny Pflughoeft May 18 at 15:15
• Good point ! Thanks – bux May 18 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 May 18 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(); – Morvy May 19 at 1:35