Need a (very) little help with 3D A* Pathfinding

I have converted morduuns genious A* 2D Grid Pathfinding Demo to 3D, but it is still a bit buggy, somebody needs to help me to fix this: the path is kinda ziczac sometimes. It finds the way and avoids obstacles etc, but still it doesn't take the shortest way (because of the ziczac line), this might be due to the way I converted to 3d in the function "evalNeighbors(,)".
The source is here: http://www.melog.ch/dl/astar3d.zip

would be very nice if some A* Gurus can help me to fix this. Thanks a lot. I'll put it to the archives as soon as this issue is fixed.

ok, fixed it.

Have you checked this A*:

http://www.blitzcoder.com/cgi-bin/articles/show_article.pl?f=turtle177610292002201622.html

IMO that's the best A* example written for Blitz.

Thank you Mustang! The code I use was written by Morduun and he mentioned it is based on Turtles A* Tutorial - so maybe this is pretty much the same.

I have a new problem now: Memory usage. Under some circumstances the Ram usage seems to explode in 3D. Especially when the path is forced into multiple S-shapes, my Machine starts to use virtual Ram on the Harddisk :)

Probably this happens because of large checklists in 3D... Maybe it's only a bug, I hope I'll be able to fix it, so I could at least precalculate the paths.

Uh - I have a new problem :)

In the Source from http://www.melog.ch/dl/astar3d.zip there is a 4-way cost calculation in use, which ignores additional costs of diagonal movement. Since I am a bit dumb if it comes to Types I need some assistance here.

This function contains the current G cost estimation:

; return the tile with the lowest F value
; F being a function of G + H, where
; G is the movement cost of a tile, and
; H is the guessed cost of movement to the goal.
Function getLowF.tile(myList.list, goal.coord)

	Local bestF% = 99999
	
	setPoint(myList, "START")
	
	For i = 1 To countList(myList)
		this.node = getPoint(myList)
		test.tile = this\parent
		
		myG = test\G + 1

		myH = getManhattan(test, goal)
		myF = myG + myH
		
		If myF <= bestF
			RVAL.tile = test
			bestF = myF
		EndIf
		setPoint(myList, "NEXT")
	Next
	
	Return RVAL

End Function

Basicly its all about the line:

myG = test\G + 1

This has to be chanched to something like

if diagonal then
 myG = test\G + 14
else
 myG = test\G + 10
endif

to check if it's diagonal it would be possible to compare x,y and z (of grid) of the tested node and the parent node. If at least 2 of them are the same (eg x1=x2 and y1=y2 etc.) then it's not diagonal.

Unfortunatel I have no idea how to access the xyz of both nodes. I know, this s noobie stuff, but I am not very familar with types :/

i did a tank game useing a* and 3d terrain its in blitzcoder under actions in the showcase section named a* tank destroyer if you want the source code leave a post in blitzcoder

Wow, cool! Thanks a lot!

I'm still trying to fix this diagonal G cost correcture...

It seems you try to get the real distance (taking into account the greater distance in diagonals).
Why don't you get the real distance from the very beginning then?
That is, replacing getManhattan by

Function getRealDist(this.tile, where.coord)
	mX = this\x - where\x
	mY = this\y - where\y
	mZ = this\z - where\z
	Return Sqr(mx*mx + my*my + mz*mz)
End Function

I confess I have not looked deeply at your code, but I guess that's what you want to achieve.
NB: I also removed this " * 1 " (!?!)

hehe the *1 was by morduun, once it might have been *10, but since all of them use *10 it doesn't matter, however.

The problem is: where.coord is of type coord, which is only the start and the goal coord. But I want to compare the test.tile to the tile which is actually the base for this test. I also don't need the real distance (tho I already use a squareroot lookup table to replace the getManhattan for the calculation of distance H), all I need is to know if I compare to a diagonal tile or to a nondiagonal tile. If I knew the xyz Index of both (not only test\x ...) I could simply check if 2 of the 3 dimesions are the same, then it would be non-diagonal. However, thanks a lot anyway!

OK, I don't really know why you need to know if it's diagonal, but retaking your idea of "x1=x2 and y1=y2 etc", isn't that what you want? Here:

diagonal = (test\x <> coord\x) And (test\y <> coord\y) And (test\z <> coord\z)

Seems toooooo easy for you to ask for help on this, but it can't hurt to give a try. If I'm still wrong, I'll just shut up, or take the time to really look at your code :)

coord is an other type. it's actually a type definition, not an instance like test. eg: test.tile vs. goal.coord

it's this part:
this.node = getPoint(myList)
test.tile = this\parent
myG = test\G + 1

but test\G is a fixed value, no matter if I compare the list end with a diagonally aligning tile or not.

however, it works with non-diagonal evaluations.

Yeah sorry, replace 'coord' by 'goal' in what I gave, that's what I meant. Well anyway as I'm not going to have the time to read and understand the whole, that's the only "help" (!) I'd have given on that. Good luck.

The coord is usually referred to as 'vector' for 3D, use that label and your code is compatible with many:)

1. Use the cost numbering scheme described by Patrick Lester: 10=horizontal/vertical, 14=diagonal. We use these numbers because the actual distance to move diagonally is the square root of 2, or roughly 1.414 times the cost of moving horizontally or vertically. We use 10 and 14 for simplicity's sake.

2. Use the standard Manhattan heuristic:

Function getEstimatedCost(this.tile, where.coord)
	Return 10*(Abs(this\x-where\x)+Abs(this\y-where\y)+Abs(this\z-where\z))
End Function

Other heuristic formulas can be found here. The purpose is not to determine the true distance but, to estimate it.

I'm having some difficulty interpreting the list-node setup. I can understand how the map.tile(x,y,z) is built. But, its difficult for me to interpret how the adjacent nodes are determined. It would be obvious that no matter how they are determined, more would be needed for the diagonal nodes.

3. IMHO I would ditch the link list structure altogether as the Pros recommend using a binary heap for faster sorting of the fcost. (and its really fast)

still analyzing the astar.bb code

I know that all, you miss the point. I am talking about G and not H. G is the cost to the next tile, H is the distance to the end point. But thanks for trying to help anyway!

jfk,

As I stated its difficult for me to interpret how the adjacent nodes are determined in your code. I really need to understand how this is achieved. From what I can see at the moment, there is no room for diagonal tiles.

If you are to determine the g cost of diagonal 'tiles, use the cost numbering scheme described by Patrick Lester: 10=horizontal/vertical, 14=diagonal. We use these numbers because the actual distance to move diagonally is the square root of 2, or roughly 1.414 times the cost of moving horizontally or vertically. We use 10 and 14 for simplicity's sake.

This will effect the proper fcost=gcost+hcost.

jfk,

Frank and the others have it right. Here's one area where you may be confusing yourself:

"G is the cost to the next tile"

Actually, G is the cumulative cost of all of the nodes (or tiles) up to that point. You find G for a particular node/tile by adding the appropriate amount (10, 14 or whatever your costing system is) to the G score of the parent of that node/tile. For more info, see that article that Mustang referenced above.

Uh, actually Blitzcoder seems to be down right now, so try this link instead:
http://www.policyalmanac.org/games/aStarTutorial.htm

That article is a basic 2D tutorial. Since your 3D characters generally walk around on 2D floors or ground, the principles are the same. If you really want to do 3D pathfinding, you can calculate the 3D distance between the nodes to come up with your G, H and F scores. But that is probably needlessly complicated.

turtle1776,

I just like to give you a direct thanks for your detailed A* tutorials. Your A* tutorials have been the only that I could comprehend. I attempted to write A* several times in the past with 0 success. Using your Beginner A* tutorial I was able to develop my own A* system with satisfactory results on the 1st try. Now I have a decent understanding of A* and other pathfinding algos.

I would be honored if you took a look at my 3D A* wippathfind.bb and provide some honest feedback. Your opinion is valued.

Thanks for the kind words. I'll try to look at it this weekend.
:)

thanks for you help. I already said very early in this thread:

"This has to be chanched to something like

if diagonal then
myG = test\G + 14
else
myG = test\G + 10
endif
"

I wouldn't write that if I didn't knew about the square root of 2 thingy, so there is no need to tell me this twice.

Frank, your socalled 3D A* Code produces an "Object does not exist" runtime error when I press 1, byside the fact that it actually is 2D A*, displayed in 3D graphicsmode, using a 2D Grid of Cubes.

jfk,

I've read through the above posts trying to figure out what your question is. Assuming you have already read the A* tutorial and understand 2D A* pathfinding, your question doesn't seem to be about A* pathfinding in general.

Instead, your question seems to be about how to modify the code of some existing A* examples to fit your game. Confusion about the particulars of the code in those examples, and unfamiliarity with types, seem to be the source of your questions.

Assuming I am right, I'd suggest contacting the authors of the code examples you are looking at and ask them to help you with the specifics. No one will understand their code better than they do. And no one else has the time or motivation to look at their code more closely.

Or ... you might just scrap the examples and code up something of your own from scratch. Meanwhile, if you have more general questions about A* or types this is a good place to ask.

I'm also not sure you really need true 3D pathfinding. It depends on what your game is. If you have a flying game of some kind, where units can fly or levitate and pretty much move in any direction at any time, I can see needing 3D. But usually flying units don't encounter fixed walls or barriers, which makes pathfinding unnecessary. A true 3D pathfinder is more likely to be useful in exploring a building with multiple stories, but even then you could use a 2D pathfinder instead, representing the building in a 3D array but only exploring nodes on another floor where there are connections (elevators, stairs).

Another variant of 3D pathfinding involves exploring a 2D world with hills and valleys on it. While different nodes may have different heights, this really has more to do with 2D pathfinding than 3D pathfinding. In this case, if you are walking up a hill or something, the 3D distance is a bit further than what it would be if your pathfinding only considered the 2D distance. But the additional cost of the node would have less to do with the small extra distance, and more to do with the additional effort required to move up a hill. This can be more than adequately simulated in a 2D pathfinder through a terrain-based penalty, which I described in that article.

I hope that helps.

jfk,

Sorry, just making sure we were on the same page. I'm working out how your adjacent nodes are created in the algo. This appears to take place in the evalNeighbors() Functions. Here is where we will determine the horizontal/vertical (10) and diagonal nodes(14). My node check is similar, but,I use a single loop with a DATA statement store adjacent offsets and gcost. The initial gcost is automatically associated with the node offset.

;You do this
For ckX=-1 To 1
For ckY=-1 To 1
For ckZ=-1 To 1
....
Next
Next
Next

;I do this
Restore Neighbors
For loop = 1 to 26
Read ckX, ckY, ckZ, ckG
...
Next

.Neighbors
;...  x,  y,  z, gcost
Data  0,  0,  1, 10
Data -1,  0,  0, 10
Data  0,  0, -1, 10
Data  1,  0,  0, 10
Data  0, -1,  0, 10
Data  0,  1,  0, 10
Data -1,  0,  1, 14
Data -1,  0, -1, 14
Data  1,  0, -1, 14
Data  1,  0,  1, 14
Data  0, -1,  1, 14
Data -1, -1,  0, 14
Data  0, -1, -1, 14
Data  1, -1,  0, 14
Data  0,  1,  1, 14
Data -1,  1,  0, 14
Data  0,  1, -1, 14
Data  1,  1,  0, 14
Data -1, -1,  1, 14
Data -1, -1, -1, 14
Data  1, -1, -1, 14
Data  1, -1,  1, 14
Data -1,  1,  1, 14
Data -1,  1, -1, 14
Data  1,  1, -1, 14
Data  1,  1,  1, 14

I hope this helps. The really neat feature about this setup is that you can make all types node offset patterns with 4-24 node offsets. I didn't realize this feature until after it was implemented.



Oops, I did find a wierd bug, that produced that error on other pcs, but, not my own. It was an illegal character in the text of the code. I believe I have corrected it. Additionally the demo is only setup to run the algo once otherwise it will produce that error as well. I'm still fine tuning and debugging.

It is true my A* operates in 2D on X/Z planes, with the Y plane controlled by gravity (set at 0 in the demo), however, it is still 3D.

Thanks. Currently I also use a neighbor checklist array very similar to your Data. But the cost is not added in the evalNeighbors() function, but in the getLowF.tile() function. Probably I better rewrite the whole thing. It's true, I am not very familar with types. I don't like types for some reasons.

jfk,

You have a pretty good understanding on how to use them. The more you use them, the more efficient you will become at their use.

I use types heavily. As matter my object-based coding technique is based entirely on them. The object-based approach has made my life as a coder easier. It is now possible for me code very large projects, because my code is organized and readible (at least to me:)).

Frank/jfk

On types: they are great, and I use them heavily, but ... using types in pathfinding for your nodes can slow things down a slight bit. Primarily this is because it takes time to allocate memory every time you create a new node with the New command, and free it up again with the Delete command. This time is very small, true, but when you multiply it across hundreds+ nodes in a single pathfinding attempt, and do path finding for dozens of units in any given frame, it becomes meaningful, particularly on older, slower machines.

That's why I use arrays for pathfinding. They are faster because once the memory is allocated, you're all set. Also, because the total # of nodes on the map are usually unchanged, you don't need all the benefits of dynamically creating and deleting the nodes.

If you are targeting more recent machines, and don't really care about the very slight performance hit, use whatever you are most comfortable with.

PS: Frank, I checked out your 3D proggy. Looks cool. How do you make the little guy move around? The mouse and the arrow keys only seem to move the camera.

I used to program a lot in assembler and I learned to organize everything from a block of adressable Ram. I love to have total control over my data, to know where everything is. Types might be useful for some stuff, but I have also seen people who are typomaniac, they try to put everything into a type, which is only complicating the Program.

Well, I have released several finished things, even without types. The CSP Engine don't includes a single type - is it a bad thing now?

Of course I worked with types several times, it's not the way that I completely don't understand them. Ok, I wonder why a type can be part of a function name (like in getLowF.tile()), but basicly I understand it. I just don't like it.

turtle1776,

The demo is pretty limited at the moment:( It only generates the path once by pressing '1'. I'm fine tuning and debugging.

I had trouble with types in the beginning as well. But once I realized how they can used, I havent been able to stop. My main reason for using them is because they are a convenient way to package Objects/Records and their properties.

;A tree object
Type tree
	Field id%
	Field typeid%
	Field trunk%
	Field leaves%
	Field fruit%
	Field region%
End Type

Prior, I used arrays for this purpose but with a strict labeling convention.

Const TREE_MAX
Dim trees%[TREE_MAX]
Dim treetypeid%[TREE_MAX]
Dim treetrunk%[TREE_MAX]
Dim treeleaves%[TREE_MAX]
Dim treefruit[TREE_MAX]
Dim treeregion%[TREE_MAX]

Using Types was a natural step for me as my coding skills evolved. Now I can see the advantages of OOP Classes in which you can package not only properties but functions as well. I attempt to mimic some OOP in my blitz coding, sticking to a strict label convention and a few rules.

Frank,

I presume that info on types was aimed at jfk? I use types quite frequently for units and whatnot, for the reasons you specify. In pathfinding, however, I prefer arrays because I think they are slightly faster (as I noted above).

I tried your demo and pressed "1" but got a memory access violation. If you put up a new version, let me know and I'll check it out.
:)

turtle1776,

I'm not sure what version you have, I did find a wierd bug, that produced that error on other PCs, but, not my own. It was an illegal character in the text of the code. I believe I have corrected it. Additionally the demo is only setup to run the algo once otherwise it will produce that error as well. I'm still fine tuning and debugging. Please advise when you downloaded the file and I'll triple check my next version and make sure the old is replaced.

BTW Frank since we are talking about your evolved coding skills and sacred OOP design - I was very impressed by your "unique color identifier method for visibility precalculation" in your FPS project roadmap documentation. Was this your idea?

Hmmm. I just downloaded the most recent version and got the same memory access violation again when I pressed "1". It may be because at home I use a 4 year old laptop that can handle most, but not all, of the latest 3D stuff. The prgram works fine until I hit "1", though, so I really don't know what's wrong. Oh well.

jfk,

LOL. The idea came to me on my own, but, others had the same idea as well. It was the first idea I had for calculating occlusion prior to understanding BSP and Portals. I've written several colorid preprocessors based on the technique since then.

I'm planning on a new version that will use pathfinding to navigate the camera through the level in the same fashion as a player. In theory, this technique should minimize the processing time because you completely avoid illegal geometry. Another idea to limit the processing time is create a agent processing module. Basically, a server distributes the level geometry between several pcs in which a portion of the level is divided. These agent pcs only perform the image capture on the portion assigned to them. Once complete the Master combines the data from each agent.

turtle1776

Sorry, I'm not sure whats wrong. But I'm hunting bugs down. Hopefully, I will be able to release something you can view.