0

I am working on images for a personal project and I stuck at a step (moreover it is a relatively easier step) My question is not related to the images by the way.

I am calculating int values for each pixel on the image. And I want to find the path with the minimum cost between to pixels (nodes). Actually I have a working implementation of A* algorithm. But I don't want to use that because I don't want to limit the "map" with nodes that you can pass or cannot pass only. I want that each node can be passed but with a cost. Some nodes will be so costly to pass, some will not. But there will be no nodes that cannot be passed.

I don't think I need to give any code because it is a very isolated part of the project. So I don't want to maniplute anybody. But basically I have a map object that has a list of nodes. And nodes have id, x,y positions. cost, neighbours (top,bottom,left and right pixels) and a node reference to know from where I came here etc.

I hope I could express the difference from Dijkstra's shortest path algorithm. How can I modify it accordingly? Or can anybody reccomend another way to do this?

Improve this question
2
  • I don't see why you need a modification. Both A* star and Dijkstra work with costs. What's the problem? Commented Apr 18, 2012 at 14:41
  • @Ishtar I think in a* there is 2 kind of nodes. nodes that you can pass, and that you cannot (walls).Am I wrong? And for Dijkstra's I don't know how to use vertices and edges. They are both same thing in my case and once you pass a node you add the cost of that node to the total cost. Commented Apr 18, 2012 at 19:24

1 Answer 1

Reset to default
2

I think I see the problem.. 'Some nodes will be so costly to pass, some will not.' That's not really how the algorithms work, you should translate the problem into nodes(with no costs) and edges(with costs). Then it should be easy to use A*, Dijkstra or any other path finding algorithm.

In your case, every pixel is a node/vertex. Every pixel has 4 edges (except for those at the borders). The cost of the edge would be the int value of the destination pixel.

Also you shouldn't keep a node reference in the nodes, it's the algorithms job to keep track of where it came from.

Hope this helps.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you. I don't think like you, I think algorithms can work for such a case. I just tried to emphasize that there will always be a path for sure. I will give the integer values accordingly, don't worry about that. I don't see the point of seperatig the nodes and edges for this example. Because if i implement like that, I think the edges will be so confusing. Because lets say x and y are 2 nodes. the cost of the edge between x and y have to be different than the cost of the edge between y and x. If you think I couldn't understand you well can you please try to explain it more?
I think you understand me perfectly. You have to make a choice, confusing edges and well known algorithms or a confusing modification of the algorithm. IMHO add the edges and then you don't have to worry about the algorithm being correct. (There are plenty of implementations available.)
Can you reccomend me a c# implementation? I found one but I think there is something wrong with that :)
I couldn't use the examples I found. It would be great if you can reccomend me a simple implementation...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.