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\$ – BlueRaja - Danny Pflughoeft May 18 at 15:15
  • \$\begingroup\$ Good point ! Thanks \$\endgroup\$ – bux May 18 at 15:28
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 May 18 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 May 19 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.