PathFinding algorithm within this implementation of a grid
Reading about Dijkstra's algorithm for pathfinding, I see that every example applicable to a "grid based" game is related to the case in which you have a "cell" that is passable or not passable. I better examplain with an image:
I need to implement an algorithm for pathfinding from A to B (returning a list of Cells to "follow") for the case II. As you can see from the image, in this model there aren't cells which are "unpassable", but every cell has stored 4 informations that determines if, while inside a cell, you can go up, down, left, right.
Searching on the net I found a lot of implementations of Dijkstra's algorithm for Case I.
- Is it possible to implement it for case II?
- If yes, can you please give me an advice?
- Should I use another algorithm for that case (The grid will be 32x14)?
Yes, it is possible. Transform your cells into a graph by modelling cells as nodes, and only connect two cells with an edge, if no wall separates them.
However, Dijkstra is not the best algorithm to use, for such an easy example. If all edges in the graph have a distance of one, you can simply use a BFS search to find the quickest path.
Additionally, the fact that the path is a grid may mean that you could even find faster algorithms to solve the problem. However, this only makes sense if your grid is really big. For your 32x14 grid, I highly doubt that a sophisticated algorithm will be faster than BFS.
- Clarification on `length = prefixTable[length - 1]` vs. `length = length - 1` in the KMP Algorithm
- Swapping two numbers using only two variables
- Fastest way to fill an array with a single value
- Algorithm for minimizing the amount of lines to draw?
- Convert Excel Column Number to Column Name in Matlab
- Find n-element in sequence. How to speed up the programm (time) for n > 10^6?
- O(n log n) algorithm to find number of large inversions
- Algorithm for drawing lines with 90-degree angles
- Depth First Search v.s. Greedy Best First Search
- How to improve pandas DF processing time on different combinations of calculated data
- How to speed up search in a huge dictionary
- Gradient Of Bezier Curve At Given Point
- How many ways can I choose numbers (repeatable) from a set that amount to the same sum?
- How can building a heap be O(n) time complexity?
- What is the reason why std::rotate() is implemented this way?
- String to string compression algorithm?
- Computing index from timestamp
- Forward chaining and Backward chaining in java
- Brent's cycle detection algorithm
- The simplest algorithm for poker hand evaluation
- Partition a string into substrings that all have majority characters
- How do I check if a number is a palindrome?
- Algorithm / pseudo-code to create paging links?
- Algorithm to draw waveform from audio
- Find the maximum number of pieces a rod can be cut
- Cycling LED Modes using ControllerMate
- How to show a sudoku solution is unique?
- Randomly Splitting a Graph according to Conditions
- How to chunk array into nice grid of rows and columns, where columns always line up (all rows are even, or all are odd)?
- Fastest sort of fixed length 6 int array