0

I have a 2D int array which I processed and got from an image. Each index can be thought as weight of that pixel. I want to find a path between 2 indexes (I'll give these indexes as input) that has the least cost. It would be great if the direction of movements can be modified (like only down&left, up&left. or all. etc. otherwise it may be down, left and right)

How can i do that in C#?

user1125953
  • 585
  • 2
  • 7
  • 18

2 Answers2

1

Regardless of language, I would calculate the cost for a direct path first. This will became the first base line. Then I would recursively search for a shorter path. You can make a few boundary checks to reduce the recursion.

  1. Any path that is >= the base line (or current best) is terminated
  2. Any path that would hit an index twice is terminated
  3. Any successful path sets the new base line (or best)
payo
  • 4,501
  • 1
  • 24
  • 32
0

The A* algorithm (as was already tagged :)) is a good choice for this.

See, for example, How to implement an A* algorithm?

Community
  • 1
  • 1
AKX
  • 152,115
  • 15
  • 115
  • 172
  • what can you say about the directions issue? – user1125953 Mar 13 '12 at 09:33
  • My intuition says that instead of allowing to add cells diagonal (or whatever) from the current cell to the list of open cells to search, allow only those that fit your constraints. It's been a while since I've used A* though, so I'm not sure it'll end up as it should... – AKX Mar 13 '12 at 09:38