Sure, bring it oncoelurus wrote:Alright, to get on-topic, who's up for a new round of ideas on pathfinding?
The Port of Dune 2 on TI 83/83+
Moderator: MaxCoderz Staff
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
3fg, my intention is never to disencourage coders, I merely show the harsh reality of rather intricate issues
Having a pathfinding competition is a great idea, since any related algo has never really been realized afaik. I haven't seen or heard of any low-resource pathfinding algorithms, other than the ones that have been discussed (I only remember that Kozak had an idea with waypoints and stuff, would be fun to read about again).
Since the current topic is possible competition material, I'll be quiet for now
Having a pathfinding competition is a great idea, since any related algo has never really been realized afaik. I haven't seen or heard of any low-resource pathfinding algorithms, other than the ones that have been discussed (I only remember that Kozak had an idea with waypoints and stuff, would be fun to read about again).
Since the current topic is possible competition material, I'll be quiet for now
-
- Calc King
- Posts: 2195
- Joined: Sun 27 Mar, 2005 4:06 am
- Location: sleeping
- Contact:
Ehm... well... I wasn't really implying that I know anything about the subject, just that I'm always eager to learn new things and to join a debate on whatever topic
On a side note, it's unlikely I will ever enter a programming competition.
On a side note, it's unlikely I will ever enter a programming competition.
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
Or continue right here, since it's a rather relevant subject for this thread?
Note that pathfinding is very variable, things will either jerk a lot or the units will have different response times (if one decides to try frame-distributed computing).
I guess that free roaming will pose a lot of problems regarding collision detection, so let's stick to a chessboard-approach (tiles, simply).
Also, buildings can plop up near anywhere, so any techniques requiring preprocessing is out of the question. Maybe one could put a limit on how close buildings may be built, or let units be able to walk on the edge of buildings? That'd solve pretty much everything, but it sure is a pretty crude solution
An unstable method is to refine paths. First, build a shortest path from A to B without considering any obstacles on the way. Start tracing the path until an obstacle is hit. Extruding two normals from the path close to the point where the obstacle was hit, look for some free space on the map. Adjust the old path by adding a "path node" in the free space. Repeat tracing and refining until a clear path has been built. Got real potential of becoming a resource hog, especially when the number of nodes and interconnected paths grow like crazy, plus the path could become pretty wacky.
Well, that's my pretty boring introducing post, gotta go to class soon
Note that pathfinding is very variable, things will either jerk a lot or the units will have different response times (if one decides to try frame-distributed computing).
I guess that free roaming will pose a lot of problems regarding collision detection, so let's stick to a chessboard-approach (tiles, simply).
Also, buildings can plop up near anywhere, so any techniques requiring preprocessing is out of the question. Maybe one could put a limit on how close buildings may be built, or let units be able to walk on the edge of buildings? That'd solve pretty much everything, but it sure is a pretty crude solution
An unstable method is to refine paths. First, build a shortest path from A to B without considering any obstacles on the way. Start tracing the path until an obstacle is hit. Extruding two normals from the path close to the point where the obstacle was hit, look for some free space on the map. Adjust the old path by adding a "path node" in the free space. Repeat tracing and refining until a clear path has been built. Got real potential of becoming a resource hog, especially when the number of nodes and interconnected paths grow like crazy, plus the path could become pretty wacky.
Well, that's my pretty boring introducing post, gotta go to class soon
- MissingIntellect
- Regular Member
- Posts: 102
- Joined: Tue 21 Dec, 2004 2:46 pm
- Location: Santa Clarita, California
- Contact: