0
\$\begingroup\$

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

grid

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):

path

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 ?

\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$ Commented May 18, 2021 at 15:15
  • \$\begingroup\$ Good point ! Thanks \$\endgroup\$
    – bux
    Commented May 18, 2021 at 15:28

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks ! That's an interesting idea. Note i maybe found another solution by using A* and determine heuristic with distance from goal. \$\endgroup\$
    – bux
    Commented May 18, 2021 at 11:31
  • \$\begingroup\$ 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(); \$\endgroup\$
    – Morvy
    Commented May 19, 2021 at 1:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .