field_of_movement algorithm is broken

[Godnoken]

Describe the bug In this particular video below, you'll see me moving between two white tiles that have the exact same cost to reach another white tile further below. However, one of the white tiles I hover is showing that it's within my field of movement, while the other one does not. The budget in this case was 5.

To Reproduce https://github.com/ManevilleF/hexx/blob/main/examples/field_of_movement.rs

Use the above example, put budget to a lower amount and look around your map to find that things don't add up

Expected behavior To be able see a field of movement that corresponds to the set budget

Screenshots Or Code snippet

https://github.com/ManevilleF/hexx/assets/17499594/e5326e70-47b2-462b-b65e-b93c11e1d0ab

---

Not sure what's wrong with it or what algorithm it is based on. I'll try to come up with a fix but I don't understand how it works yet.

[ManevilleF]

@orph3usLyre this might interest you

[Godnoken]

I came up with a working solution using the Dijkstra algorithm. I can try to implement it in a similar coding style as the current state of field_of_movement, however, it may take a little while as we're heading into Christmas festivities.

Merry Christmas!

[ManevilleF]

Looking into this, and yeah the algorithm is definitely broken, an actual pathfinding algorithm should be used instead

[Godnoken]

Hi again,

I lack the time & probably the skill currently to convert my solution to something that looks more Rust idiomatic. But I'll post my solution below and hopefully that can help some;

fn field_of_movement(
    start: Hex,
    budget: u32,
    cost: impl Fn(Hex) -> Option<u32>,
) -> HashMap<Hex, (Hex, u32)> {
    let mut priority_queue = BinaryHeap::new();
    let mut cumulative_costs = HashMap::new();

    priority_queue.push(((start.x, start.y), 0));

    while let Some((current_hex, current_cost)) = priority_queue.pop() {
        let hex = Hex {
            x: current_hex.0,
            y: current_hex.1,
        };

        let neighbors = hex.all_neighbors();

        for neighbor in neighbors {
            if let Some(edge_cost) = cost(neighbor) {
                let total_cost = current_cost + edge_cost + 1;

                let current_cumulative_cost = *cumulative_costs
                    .get(&neighbor)
                    .map(|n: &(Hex, u32)| &n.1)
                    .unwrap_or(&std::u32::MAX);

                if total_cost < current_cumulative_cost && total_cost <= budget {
                    cumulative_costs.insert(neighbor, (hex, total_cost));
                    priority_queue.push(((neighbor.x, neighbor.y), total_cost));
                }
            }
        }
    }

    cumulative_costs
}

The reason why I'm returning HashMap<Hex, (Hex, u32)> here is so one can easily use a helper function to find the shortest path to any tile within the field of movement.

pub fn get_path(target: &Hex, parents: &HashMap<Hex, (Hex, u32)>) -> Vec<Hex> {
    let mut rev = vec![target.clone()];
    let mut next = target.clone();
    while let Some((parent, _)) = parents.get(&next) {
        rev.push(parent.clone());
        next = parent.clone();
    }
    rev.reverse();
    rev
}

[ManevilleF]

Hey @Godnoken could you check #142 ? I think it fixes the problems

[Godnoken]

Hey @Godnoken could you check #142 ? I think it fixes the problems

Hey bud,

I'll try to take a look at it within the next few days. I'm currently travelling in the UK :)

[ManevilleF]

Closing for now, feel free to reopen if necessary