TR Forums

Hey guys, I've been trying to make a pathfinding algorithm (of which I'm sure there are many better ones out there with more braintime poured into them but whatever), and I realized that I need a history >1 element deep if I'm going to search all 8 neighbouring pixels around every pixel.

The problem is how do I implement this. If white pixels represent the path, then the oldest white pixel added to this data element should be deleted if adding a new one would exceed a predetermined size of this data element. The problem is what is this data element? A queue sounds like the solution, but according to cplusplus.com a queue doesn't let you look at the values of the elements in between the first and last element. I need to compare the position of a white pixel with at least 5 positions of other white pixels to prevent the algorithm from chasing its own tail. But cplusplus says you can only access the front and back of a queue, and everything in between is... well, you can't look at it to compare the positions. So what should I do?

Perhaps std::list or std::deque instead of using a queue? These containers allow you to access the individual elements but have different strengths and weakness in accessing, inserting and deleting elements.

Yeah, I'd look at a linked list before a queue.

bthylafh wrote:

Yeah, I'd look at a linked list before a queue.

Possibly a circular list implemented atop an array, depending on how important the performance vs code clarity tradeoff is.

A four or eight dimensional bidirectional linked list. Eight if you can move diagonally. Each node in the list represents a decision point in your path. The forward link represents a direction to try and is null if not tried and points to the current node if the direction is not valid. The back link for each direction points to the node from which you came. This represents your backtrack path. The special case of the direction that has a null follow link and a non-null backtrack link will represent the direction from which you originally entered the intersection and is the direction you go when all other directions have failed. If there is only one way in and out of a point on the path, then you don't have to add it to the list.

You may want to add another pair of pointers that organize the whole think as a regular linked list as well so that deletion of all the points is reasonably easy.

--SS

Well guys, it's been two weeks since then, and I've found that my algorithm... kinda sucks. Probably should've just used A* or something like that. But I figured that if I just make a list of all the white pixels in an image, and make the user go over each and every white pixel with the physical tool (of course, once translated into the image coordinate system), it'll be good enough for my purposes for the time being.

So I think I'll make an array of the positions of each white pixel, and since finding all the white pixels in the image will probably give me a count of how many white pixels there are as a byproduct, I can use an array in this case.