2D Path Finding
Blitz3D Forums/Blitz3D Beginners Area/2D Path Finding
| ||
| Alright, so I've never really paid attention, but it turns out I know absolutely nothing about Path Finding..shocker aint it? I'm trying to find a way to do it with types. For Example(Probably not a working code - warning): Note: Half Pseudo Code because my problem right now is figuring out which one is closest to PlayerX, Yea thats kinda noobish, but I've never paid attention to such things, so I gotta start learning. Another Note: Reason this post is in Blitz3D is I hear some of blitz3d functions don't work in BlitzPlus(and vice-versa ) so I posted it here. ;This function doesn't work cause its pseudo code! :D Function Search() If P\X / 32 =< 20 Then If N\X Is Closest to P\X Then MX = MX + N\X If N\Y Is Cloest to P\X MY = MY + N\Y End Function ;this should work lol For T.Tile = Each Tile If T\O = 1 Then N.Node = New Node N\X = T\X N\Y = T\Y Next Anyway, you get what I'm trying to explain, I hope. So, how do you guys do it, I'm looking for a little insight because as stated before, these are the "small" things I never paid attention too. Last edited 2010 Last edited 2010 |
| ||
| Pathfinding is a Science discipline by its own. Seek for the socalled A-Star ALgorithm ("A*"), it's a sofisticated way of path finding. Although most of the algorithmic path finding is rather slow, especially when ported to 3D. When only 2D is used, A* may be the easiest way to do it. There may be other solutions and hybrid mixes of waypoint lists and algorythmic pathfinding. What works best in 3D IMHO is a grid of waypoint lists with crossing-sections. The best connection between any pair of crossing sections will be precalculated and stored in a lookup table. The seeker will then only have to go to then next crossing section and then follow the waypoints and/or crossing section list stored in the lookup table. |
| ||
| I wrote one once where i stuck a load of pivots down and then made the "seeker" turn towards them by deltayaw. However the amount of datayaw was offset by a random value of between -1 and +1 degrees and updated once a second using the millisecs(). the pre defined "acuraccy value" when futher away from 0.00 had the desired effect. Once seeker was was within the required distance to target it would seek the next one and so on. I suppose for 2d you could do something similar with 2d waypoint coords and some simple math. However f you mean "maze pathfinding" then i am no help at all, and wouldntnt know where to start on that one. :D Perhaps something like the above with a bigger deviation -90-+90 when obstacles hit? Last edited 2010 |
| ||
| http://blitzbasic.com/codearcs/codearcs.php?code=1488 Here is a simple algorithm I wrote a very long time ago, based off something I did even longer ago. Read through it. It works. another method: Pathfinding in 2d with a grid is pretty easy actually. A simple method is to recursively step outwards from the starting position on the grid, only going to walkable squares. In a second grid store the number of steps taken (minimum) to get to that square. When the target grid node is reached simply trace back by the numbers. Alternatively start the search from the target node and work back to the starting node. |
| ||
| Don't use types. I found them to be alot slower than an array :) |
| ||
| I agree, although i comprimise on that because using arrays is like going back to lighting fires with sticks. (ie only do it if ABSOLUTELY nessecary :D) If i have codeblock with lots of references (perhaps more than 10) I copy the fields i need to local variables at the start of multiple referencing, do all the hard-processing using those. Then I copy -only- those that need to be updated them back at the end . This can really cut down the number of times it has to look up the values from the type. eg. function DoSomething( ship.MainShip) ; <--- or could be start of an intense loop handle = ship\handle posx = ship\PosX posy = ship\PosY ...lots of logic involving posx,posy,handle... ship\Posx = posX ship\Posy = posY end function ; or loop Last edited 2010 |
| ||
| When I did my pathfinding, i was temp creating new types and reordering some of them. Compared to my array version, is was about... 2 or 3 times slower? Bad coding on my part, probably, but still :) |
| ||
| Field lookup is fast (although D4NM4N's method of using local temps is valid enough if you're really forcing every last drop of power out - the threshold for this is around 7-10 references I think) - it's faster than array access in all cases. Object creation and deletion is a lot slower than array access, in all cases. It's a matter of the right data structure for the right task: linked lists like the global type list simply aren't appropriate for quickly indexed access. You might notice an across-the-board improvement though if you put your objects into an array; constant lookup time per-object, and then all your fields are in one, easily-extensible place. (To a large extent many people could make a coherent argument - I won't try though - that if you aren't using cutsom types, you're doing it wrong; since programming is so closely connected to type theory, all functionality can essentially be brought down to strong typing. Not using strong typing is therefore making life unnecessarily complex) |
| ||
| I see the only positive aspects of types in their fexibility. But as soon as when it comes to speed-critical execution I will use custom made structs in a bank or an array instead. Doing a "For Each" Loop won't give you access to the index directly, but the index is often needed for high speed operations. Especially the continous creation and deletion of types is really unneccessary slow. In this case I would easily sacrifice a meg or two of ram, when a static array of a certain size can do the task in a faster way. |
| ||
| if memory is a problem use types, otherwise use arrays :) |
   |