MaxCoderz

coelurus wrote:Alright, to get on-topic, who's up for a new round of ideas on pathfinding?

Sure, bring it on

Do we have a new competition subject here? .

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

Oh I know you didn't mean to discourage. You were just pooping on my parade. If you hadn't done that though, I might have invested a lot of time into the program before hitting that particular snag, and wasted lots of it.

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.

Hhmm... come to think of it, i cant see too many people entering a programming comp based on Pathfinding.

Maybe we should just open a discussion thread about it?

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

I know this is off-topic, but don't worry about how good your English is; most Americans suck at English.

Like me eh?

@coelurus: Great example, I have thought of this before a little. I hope to see others contribute to pathfinding ^^.