Implementing history in pathfinding algorithm

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Implementing history in pathfinding algorithm

Postposted on Sun Jul 17, 2011 5:07 pm

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?
Mothership: Thuban 1055T@3.7GHz, 12GB DDR3, M5A99X EVO, GTX470+Icy Vision Rev.2@840/3800, Vertex 2E 60GB
Supply ship: Sargas@2.8GHz, 12GB DDR3, M4A88TD-V EVO/USB3
Corsair: Macbook Air Ivy Bridge
Crayon Shin Chan
Minister of Gerbil Affairs
 
Posts: 2246
Joined: Fri Sep 06, 2002 11:14 am
Location: Malaysia

Re: Implementing history in pathfinding algorithm

Postposted on Sun Jul 17, 2011 5:51 pm

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.
accord1999
Gerbil
 
Posts: 58
Joined: Thu Jul 22, 2004 6:25 pm

Re: Implementing history in pathfinding algorithm

Postposted on Sun Jul 17, 2011 6:23 pm

Yeah, I'd look at a linked list before a queue.
Think for yourself, schmuck!
i5-2500K@4.3|Asus P8P67-LE|8GB DDR3-1600|Powercolor R7850 2G|1.5TB 7200.11|1988 Model M|Saitek X-45 & P880|Logitech MX 518|Dell 2209WA|Sennheiser PC151|Asus Xonar DX
bthylafh
Grand Gerbil Poohbah
 
Posts: 3189
Joined: Mon Dec 29, 2003 11:55 pm
Location: Southwest Missouri, USA

Re: Implementing history in pathfinding algorithm

Postposted on Sun Jul 17, 2011 10:49 pm

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.
UberGerbil
Gerbil Khan
 
Posts: 9993
Joined: Thu Jun 19, 2003 3:11 pm

Re: Implementing history in pathfinding algorithm

Postposted on Mon Jul 18, 2011 7:30 am

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
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1719
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Implementing history in pathfinding algorithm

Postposted on Fri Aug 05, 2011 4:06 pm

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.
Mothership: Thuban 1055T@3.7GHz, 12GB DDR3, M5A99X EVO, GTX470+Icy Vision Rev.2@840/3800, Vertex 2E 60GB
Supply ship: Sargas@2.8GHz, 12GB DDR3, M4A88TD-V EVO/USB3
Corsair: Macbook Air Ivy Bridge
Crayon Shin Chan
Minister of Gerbil Affairs
 
Posts: 2246
Joined: Fri Sep 06, 2002 11:14 am
Location: Malaysia


Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 1 guest