Member Avatar for ajhais

Given a n*n grid with free spaces and obstacles in the form an n*n integer matrix. We need to find shortest between any two given points (x1,y1) and (x2,y2) through the free spaces. We are not allowed to move in diagonal. Please help me figuring out an algorithm for doing this.
Thanks in advance.

  • 4 Contributors
  • 7 Replies
  • 127 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by Prabakar

Dani AI

Generated

As pointed out, for an unweighted n×n grid with 4-way moves the correct way to guarantee a shortest path is breadth‑first search (BFS). BFS expands nodes in increasing distance from the start, so the first time it reaches the goal is along a shortest route Breadth-first search. is right that DFS will find a route, but DFS does not guarantee shortest paths; Dijkstra also finds shortest paths but on unit-cost grids it reduces to BFS Dijkstra's algorithm.

Practical BFS notes:

  • Represent the map as an occupancy grid (free/blocked), keep a boolean visited array and a parent pointer per cell to reconstruct the path.
  • Enqueue the start, mark visited when enqueued (prevents duplicates), and stop as soon as the goal is dequeued.
  • Reconstruct the shortest path by following parent pointers from goal back to start.
enqueue(start)
visited[start] = true
parent[start] = null
while queue not empty:
  u = dequeue()
  if u == goal: break
  for each 4-neighbor v of u:
    if inBounds(v) and free(v) and not visited[v]:
      visited[v] = true
      parent[v] = u
      enqueue(v)

For dynamic maps (Battle City type): rerun a fast search only when the current path becomes blocked. For faster replanning use A with an admissible Manhattan heuristic for 4-way movement (optimal and much faster than blind BFS) [A search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm), Manhattan distance. If obstacles change frequently and you need incremental replanning, consider incremental search algorithms such as D Lite which reuse previous search work [D Lite]().

Implementation cautions: keep bounds checks, avoid revisiting, limit search radius if CPU is constrained, and combine global planning (A/D Lite) with simple local avoidance to handle very short‑range sudden obstacles.

Recommended Answers

All 7 Replies

Member Avatar for csurfer

Given a n*n grid with free spaces and obstacles in the form an n*n integer matrix. We need to find shortest between any two given points (x1,y1) and (x2,y2) through the free spaces. We are not allowed to move in diagonal. Please help me figuring out an algorithm for doing this.
Thanks in advance.

Well this is one of the many ideas you can apply to this problem.Here it goes:

Firstly take the value of n for your n*n grid from the user and also a valid grid structure input where free spaces are represented by 1's and obstacles are represented by 0's.

Your array for 4*4 might look like this:

0 1 2 3
0  1 1 0 0
1  0 1 0 0  
2  1 1 1 1
3  0 1 1 1

Now pass this array as input array and (x1,y1) as input co-ordinate
and (x2,y2) as the destination point to be reached for a "DEPTH FIRST CHECK" graph algorithm.

Actually the best graph algorithm to find the shortest path between two vertices is "DIJKSTRA'S ALGORITHM" but here as you are just moving one step to top bottom left or right only and all steps are of same length you can use Depth First Search only to solve your problem.

Member Avatar for ajhais

Well this is one of the many ideas you can apply to this problem.Here it goes:

Firstly take the value of n for your n*n grid from the user and also a valid grid structure input where free spaces are represented by 1's and obstacles are represented by 0's.

Your array for 4*4 might look like this:

0 1 2 3
0  1 1 0 0
1  0 1 0 0  
2  1 1 1 1
3  0 1 1 1

Now pass this array as input array and (x1,y1) as input co-ordinate
and (x2,y2) as the destination point to be reached for a "DEPTH FIRST CHECK" graph algorithm.

Actually the best graph algorithm to find the shortest path between two vertices is "DIJKSTRA'S ALGORITHM" but here as you are just moving one step to top bottom left or right only and all steps are of same length you can use Depth First Search only to solve your problem.

Hi.. thanks for the solution. I was thinking of going with the same.. How can we approach this problem if the map is dynamic.. that is if some obstacles can randomly appear in the map.. We actually need to code a bot for battle city game..

Member Avatar for csurfer

Hi.. thanks for the solution. I was thinking of going with the same.. How can we approach this problem if the map is dynamic.. that is if some obstacles can randomly appear in the map.. We actually need to code a bot for battle city game..

Well if you know DFSearch then you will know that each time the whole array gets passed as one of the function argument to the recursive DFSearch function and checking is done in a for loop.
So before checking in the for loop in case of dynamic obstacles just change the particular

Array[<i co-ordinate>][<j co-ordinate>] = 0;

before passing the array to next DFS function recursively.

Member Avatar for nucleon

ajhais,
It should actually be a Breadth First Search (BFS), not a DFS.

Member Avatar for csurfer

ajhais,
It should actually be a Breadth First Search (BFS), not a DFS.

No its a DFS only not BFS : You don't need to move to all points adjoining a point,if you wanted to do that then BFS is required. But in this problem we want to move through different blocks taking steps moving away from start point so we need DFS where once we reach a point then we need to take a step towards destination not worrying about the other points reachable from that point.
After all evaluation we need to find the shortest path.

Member Avatar for nucleon

I don't feel like arguing. Can someone else weigh in on this? DFS or BFS?

Member Avatar for Prabakar

If you know that there is a way, why not go for it, why should one try all the ways possible? If you are lucky you would have chose the right path the first time. I would go for DFS. I believe one should use a stack and not queue.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.