A* and Dijkstra's pathfinding algorithm using Torquescript?

#1 I'd say its definately possible though for efficiency any major pathfinding would probably want to be done in C++... I've just barely started at th is so can't give too much input...

#2 Yup, it is.
I've done it, although it's not particularly efficient. I think "exodus" has done it as well.
It's slow, and you're probably better off trying to find a way to do it in C++.

#3 Hmm... waypoint pathfinding shouldn't be too inefficient for a pacman type game though, right? I think breadcrumb pathfinding starts to get too complicated for it to handle... But as far as saying I'm better off at doing it in C++, my lack of programming skills just let loose a tiny scream of pain when I read that. I have zero C++ experience. The last bit of programming experience I've had was in Commodore 64 BASIC :). Good luck to me.

Thanks for the info.

#4 I might be looking at a way to create more universal T2D configurable pathfinding (maybe make some sort of in game editing to tweak what to avoid using different algorithms, etc etc)... again this is a big might and If so I will probalby consider either selling (for a very small price) as a code add on, or package it with something... since this would demand a decent bit of work... looking at combining with someone doing an art pack also....

#5 Click here if you want to look at an A* library for C++ and Blitz Basic.

Heh, my eyes just glazed over, looking at the library and thinking of using torquescript.

However... I still think waypoint pathfinding is very doable in torquescript (even though I still don't know how to do it at all). I have a long way ahead of me...

#6 If anyone is taking an active role in working on pathfinding in T2D, please send me an email (King Bob?). I'm working on the same concept for the RTS-SK in my spare time, and have some suggestions/guidance from GG that will probably apply here as well.

I can't promise any expected timelines at -all- for either the RTS-SK or T2D--this keeps getting pushed back unfortunately, but it would be good to not re-invent the wheel for each of the TAP platforms!

#7 A* is on my list to be done but I haven't tackled it yet. I'm 100% sure I can do it in TorqueScript though. Why? Because its a challenege and I love pushing Tscript to the edge so i'll find a way to get it done :)

Probably within the next couple weeks i'll be doing this. Its something i've wanted to do ever since I got T2D.

#8 I wrote an interpolation system in TorqueScript just to prove it could be done. It can. It's slow. I really don't recomend doing something like this in Torque Script.

#9 Looks like i'll be tackling this much sooner than expected as I need a basic A* algo for some stuff in TileIt.

#10 Luckily, A* is complete overkill for my game. I'm going to try a waypoint system. I believe script should be able to handle that easily. But it'd be nice to have something like A* find the shortest routes in my waypoint system for me :). With 50 waypoints, it becomes a big task for each stage to manually do. But once figured out, it should save a lot of computational resources.

It'd be nice to add a breadcrumb system to that, but I'm just getting greedy. Good luck on your A* usage in TileIt. I'm pretty excited about that game.

#11 If A* is too slow for use at runtime and if the map is static (ie the interconnectedness of the waypoints and the cost to move between them doesn't change during a game) one could precalc movement costs into an array (that will be loaded from disk when playing).
Have say starting waypoints as rows, and destination waypoints as columns. Store the next node to go to in the table. Then you do a complete pathfind with several lookups:
Say I want to go from node 1 to node 10. Row and column tells me that the next node from 1 is 5. Go there and do another lookup from 5 to 10 etc etc.

#12 Yes, that's what I was planning to do. There's a problem in my game design, however, that makes this not so simple. The player is able to create walls in any location of the maze that he chooses. This can make the waypoint data worthless, because of the new obstacle. Unless there's a way to find out which waypoints are cut, and ... no... because it's depending on the coder to tell it ahead of time which paths are best. It doesn't think at all. I don't know...

#13 I'm going to make some tutorials of making derivative fxSceneObject2D in C++ for your own custom objects... I'm considering mathing a path node and a path finder object that will allow you to place path nodes than find a path between each node so you can save out the paths... just putting down some of my thoughts :)

#14 There is an implementation of Dijkstra in TorqueScript already.... it was for TGE, but it's something to look at.

www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=6051

#15 @Matthew
That sounds wonderful! Thank you very much for any and all tutorials you make. They're worth a lot to me. And this would be perfect for my plan.

@Harold
Ohh, lovely. I'll look at this. Thank you.

#16 Just wanted to post saying that my extremely basic and probably inefficient implementation of A* is almost complete. Hopefully it'll be done within the next few days at the most and i'll be sharing it with the community. Only rule is no laughing :o

Its the first time i've ever tried to actually implement this routine.

#17 Wonderful. I can't wait to check it out.

#18 I now have this completely implemented. I'm actually surpsied at how well it works to find a path. Given my test map of 5x5 tiles, it almost never seacrhes any extraneous tiles.

I'll release it soon, but first I need to clean it up and comment it.

#19 The resource has been submitted. Of course it will take a while before its approved but if you don't want to wait, click here.

#20 Are there any updates to this resource? It seems to be finding paths, but not the shortest ones I'm afraid...

cheers,
Arkadesh