[Feature]: Dijkstra pathfinding algorithm

[bal7hazar]

Feature Request

Implement Dijkstra's (source) algorithm for the map package.

Here: https://github.com/dojoengine/origami/tree/main/crates/map/src/helpers

Proposed Solution

No response

Alternatives

No response

Related Code

No response

Additional context

Currently the A* algorithm is implemented, having the choice to use different algorithm for specific cases could be interesting.

Try to match the A* trait for the high level usage, such as:

fn search(grid: felt252, width: u8, height: u8, from: u8, to: u8) -> Span<u8>

If the feature is accepted, would you be willing to contribute it?

• [ ] Yes I would be willing to contribute

[bengineer42]

I could do this at some point after the residency if no one has by then

[cryptogru725]

I'd like to handle this task.

[JJScar]

I’d like to resolve this.

[Sumitpalekar]

Is this issue still available?

[bengineer42]

This is still available

[cryptogru725]

I'd like to contribute to this issue.

[JJScar]

Can I work on this, please?

[sanwalsulehri]

Can I try solving this issue?

[7-falseparfait]

Could I take a shot at this?

[JuViquez]

I'm Julio from Costa Rica and part of Dojo Coding community.

I haven't implemented Djikstra since college haha. I think it would be a fun experience for me since I'm completely new on Only Dust and also with Cairo, sounds like a challenge :).

Regarding my proposed implementation, I'd create a new file under 'origami/crates/map/src/finders' called djikstra.cairo. I'd also add a new abstraction called something like 'PathFindingAlgorithmTrait' to classify the new Djikstra and A* under a single trait.

The estimated time for implementation would be probably 3 days, I'm completely new so setting everything up will probably take me some time :(.