Help needed in finding a bug in my path finding code.

[Bugala]

I have this Pathfinder code, and it almost works:

Code: Select all

Function p_PathFinding(location, distance)

Local t_location = locationcards[location]
If t_location.destroyed = True Then Return

Local found = False
ForEach(t_havedistancealready, Function(index, t_place)
				If t_place.name = location And t_place.distance =< distance Then found=True
			       EndFunction)
If found = True Then Return
	
Local t_temp = {name=location, distance=distance}
InsertItem(t_havedistancealready, t_temp)

If distance = currentshortestdistance And t_location.type = "mountain"
	InsertItem(t_closestmountains, location)
ElseIf distance < currentshortestdistance And t_location.type = "mountain" 
	currentshortestdistance = distance
	t_closestmountains = {}
	InsertItem(t_closestmountains, location)
EndIf

Local amount = ListItems(t_location.neighbors)
For n=0 To amount-1
	p_PathFinding(t_location.neighbors[n], distance+1)
Next
EndFunction

Before I call it, i make t_havedistancealready and t_closestmountains empty tables and i make currentshortestdistance = 100.

And when i make the call, i call it with p_PathFinding(location, 1)


problem with this code is, that it doesnt go through every location, and after having spent last 3 hours trying to hunt that problem down, I decided it was better to ask if one of you can see the problem with my code.

Each location has neighbors, and hence every location is connected to every location through some path, and therefore every time this pathfinding is executed, it should give distance to each location. But at worst it might check only 4 locations in total and i cant figure out the logic of why, even i have the names of those locations making it possible for me to follow the execution using debugprints.

oh, and just to make it more clear. The real purpose of this function is to find closest mountain locations, but it is just in practice done in such way that it shold go through every location.


Can anyone spot my error?

[jalih]

Should this shortest path search be more like a finding the shortest path from network of nodes or finding a path on map?

For finding the shortest path from network of nodes I have some old PL/I code to do the job and could probably make a Hollywood version, if needed.

What comes to finding the shortest path on map, there is there is a A* source that can be used as a starting point located inside my game framework.

[Bugala]

I guess answer would be nodes. (not sure about the difference).

You could think it as RISK games map. There are areas (as example, could be Finland) and then they would have neighbors, as example (Sweden, Russia, Norway).

Then some of the areas are marked as being Mountains (lets say, Switzerland).

Then I could be looking for closest mountain location from Finland, which could be for example, Poland.

Also, Distance is not real distance, but Area distance.

Meaning that German is much further away from Finland thatn China, since to get to Germany, you need to go through several areas, while China is only two steps away (Finland-Russia-China).

[jalih]

Test this Windows demo written in PL/I.

Instructions:

Program will first ask you to insert links to city nodes. You must use the format provided in example or else you will get a conversion condition as it uses list-directed I/O.

example:
'Finland' 600 'Sweden'
or
'Finland', 600, 'Sweden'

After you have done inserting links to city nodes, press Control+Z keys.

The program displays all the nodes with links and ask you to insert destination node. Again remember, we are still using list-directed I/O to read input.

After that, it will ask you to insert start node and displays shortest route to destination node. Again remember, we are still using list-directed I/O to read input.

Press Control+C when you are done.

Is this kind of shortest route finding what you are after?

[Bugala]

It is quite close to what I am looking for.

But to give better example, heres picture of RISK games map: http://www.game-en-co.nl/wp-content/upl ... Risk-1.png

What my code is supposed to do, is following.

Although I am using RISK board as example, the game is not RISK. In my game, players are in one area at once, and they can move around.

One of the event cards work in such way, that each player needs to move to the closest mountain location.

Hence I am making following example:

Suppose player is standing at EAST AFRICA.

Then he gets a event card that tells that he needs to move to the closest location that has a unit in it.

Now this pathfinding code of mine starts looking for it. And it should notice that NORTHERN EUROPE is the closest location with a unit, since it is only 2 steps away (as example: EAST AFRICA - EGYPT - NORTHERN EUROPE).

However, he could be instead standing in WESTERN UNITED STATES, in which case code should notice there are actually three possible locations of: ALASKA, GREENLAND, VENEZUELA, each of them, 2 steps away.


You can see in my code that I am using this t_closestmountains as a table that will hold each possible closest location in it, so i can elsewhere in code handle giving the player a choice in choosing which one he wishes to pick as the location to move to.



My pathfinding works quite simple. It starts from location where the player is standing and basically says that locations distance is 0 (that is not shown in this code).

It then goes to each neighboring location, and says that their distance is 1 further away, making distance 1.

As it executes all those neighbors, it tells to go to each of their neighbors again, and make distance 1 further, making distance become 2, and this how it continues forever, until all locations (24 in total) have been checked through. However, for some reason it doesnt go through each location.

This system alone would make it loop forever, as you get from lcoation A to B, and from B to C, and from C to A, then it would continue looping forever. However, for that there is this t_havedistancealready where each location that havent been executed before is marked up, to avoid it being executed twice (although some will be exectued twice by purpose actually).

Exception to not executing same location twice is, if the new route is shorter than previous stored locations distance is.

This means that if A is connected to B and D, B is connected to C and C is connected to D, it might first take route of A-B-C-D and mark its distance as 3 steps from A, but then later when it continues executing Bs neighbors, it ends up to D again, but this time with distance of only 1, hence it will look that while D have been executed already once, it was however longer distance, and therefore D should be allowed to be executed again.

[Bugala]

I just noticed I posted one unnecessary line of code:

Code: Select all

If t_location.destroyed = True Then Return

ignore this line, since it has to do with the actual program and when looking just this pathfinding part, you dont need it.

Also, better explain the next line too:

Code: Select all

Local t_location = locationcards[location]

Idea is that you pass down just the name of the location, and when it enters this pathfinding function, it will find the Table that contains all the info about this location (t_location). I have stored or locations info tables inside locationcards[name].

Hence this line.

[Bugala]

I found the bug. No wonder I had trouble finding it, I had misunderstood how Hollywood works.

looping with:

Code: Select all

for n = 0 to amount-1

Meant that "n" was global variable. Hence it didnt execute for-next loops separately but kept changing Ns value and when it got to the end on any loop without continuing to next for-next loop, then it ended there.

Fix was:

Code: Select all

for LOCAL n = 0 to amount-1

I always thought for-next loops variables are automatically local variables. Good to know this for future.

[jalih]

I found the bug. No wonder I had trouble finding it, I had misunderstood how Hollywood works.

Good, that you got it figured out!

I would still recommend using some kind of a tree structure to store the game map data as network of nodes for Risk style game.

I wrote you a little example. It also serves as an example on how to handle list data structures by your self without using Hollywoods built in functionality. As tables are reference types, you can do all that lovely pointer stuff you thought you could live without!

Code: Select all

Const #INFINITE = 32767


city_head = Nil


Function setup(city1, dist, city2)
	connect(city1, dist, city2)
	connect(city2, dist, city1)
EndFunction



Function find(city)
	Local p = city_head
	While p <> Nil
		If p.city_name = city Then Return(p)
		If HaveItem(p, "city_list") Then p = p.city_list Else p = Nil
	Wend
	Local p = {}
	p.city_name = city
	p.city_list = city_head
	city_head = p
	p.total_distance = #INFINITE
	p.route_head = Nil
	Return(p)						
EndFunction


Function connect(source_city, distance, destination_city)
	Local s = find(source_city)
	Local d = find(destination_city)

	Local r = {}
	r.route_distance = distance
	r.next_city = d
	If HaveItem(s, "route_head") Then r.route_list = s.route_head Else r.route_list = Nil
	s.route_head = r
EndFunction


Function print_all()
	Local p = city_head
	
	While p <> Nil
		DebugPrint(p.city_name.. ":")
		Local q = p.route_head
		While q <> Nil
			DebugPrint(q.route_distance.. " miles to ".. q.next_city.city_name)
			If HaveItem(q, "route_list") Then q = q.route_list Else q = Nil
		Wend			
			
		If HaveItem(p, "city_list") Then p = p.city_list Else p = Nil		
	Wend
EndFunction


Function shortest_distance(destination_city)	
	Local bestp, d, bestd, p, q, r
	
	Local p = city_head
	While p <> Nil
		p.total_distance = #INFINITE
		p.investigate = False	
		If HaveItem(p, "city_list") Then p = p.city_list Else p = Nil
	Wend
	p = find(destination_city)
	p.total_distance = 0
	p.investigate = True
	Repeat
		bestp = Nil
		bestd = #INFINITE
		
		p = city_head
		While p <> Nil
			If p.investigate
				If p.total_distance < bestd
					bestd = p.total_distance
					bestp = p
				EndIf
			EndIf
			If HaveItem(p, "city_list") Then p = p.city_list Else p = Nil
		Wend		
		If bestp = Nil Then Return
		bestp.investigate = False
		q = bestp.route_head
		While q <> Nil
			r = q.next_city
			d = bestd + q.route_distance
			If d < r.total_distance
				r.total_distance = d
				r.investigate = True
			EndIf
			If HaveItem(q, "route_list") Then q = q.route_list Else q = Nil
		Wend	
	Forever

EndFunction


Function print_route(source_city)
	Local q, t, d
	Local p = find(source_city)
	
	Repeat
		t = p.total_distance
		If t = #INFINITE
			DebugPrint("(No connection)")
			Return
		EndIf
		If t = 0 Then Return
		DebugPrint(t .." miles remain, ")
		q = p.route_head
		While q <> Nil
			p = q.next_city
			d = q.route_distance
			If t = d + p.total_distance
				DebugPrint(d .." miles to ".. p.city_name ..".")
				q = Nil
			Else
				q = q.route_list
			EndIf
		Wend		
	Forever
EndFunction

;*******************************************************************************
; Demo starts here
;*******************************************************************************

; Setup links between cities
setup("c1", 10, "c2")
setup("c2", 5, "c3")
setup("c1", 19, "c4")
setup("c3", 5, "c4")

; Display all cities and connections 
print_all()

; Calculate shortest distance to c4
shortest_distance("c4")

; Display the result from c1
DebugPrint("\nThe shortest route to destination:")
print_route("c1")