Slick Forums

My previous post didnt come trough for some odd reason, anyways:
Im looking for a good method for pathfinding in a rts game, all i can find is A*. However i dont want to use tiles, i want to give the user more freedom in building, and positioning of the units. I dont necesarily need to mouve in formations, but i do want to move selection of units. Another way is Dijkstra's Shortest Path Algorithm. What other algorithms are there useful for pathfinding? Ive searched a lot, and cant seem to find anything of use for me (there was only 1 other topic on this forum about non tiled based path finding).

Any help would be greatly appreciated!

Anybody? i really need some help with this D:. There seems to be a great pathfinding api, but this is all for tiled gameplay.

Well, I don't know much about non-tiled pathfinding. It's probably very hard to implement, which could be why most strategy games are based on tiles (whether these tiles are visible to the player or not). Right now I can't think of one rts which doesn't use tiles (could you please mention one?).

I don't know how your game is like, but I can't really think of a game where not being able to place your building exactly where you want to is a big issue. Most of the time you could probably get away with using small tiles.

Anyway, the only way that I can think of is to use some sort of Quadtree. Starting with big tiles and then splitting them into smaller ones when needed, thus allowing you to place the buildings on the exact pixel you want to. Now, this is just a thought I i had. I have no idea if this is possible without slowing down performance too much. I don't know how to implement it either, so I can't help you any further.

Eitherway, good luck. If you figure something out, I'd love to hear about it.

Well i have no clue how i can move objects correctly otherwise? i mean, i dont want units only to be able to walk into 9 directions, that would look kinda silly? Unless there is a way to fix that?
Starcraft for example, the units move in a nice line straight to their destination, the buildings are placed on a grid however. Or do i just need an insanely big grid? But this would be really bad performance wise i suppose?
http://www.youtube.com/watch?v=AZxVXqQq ... ure=relmfu
And no the buildings dont have to be precise on some places i suppose.

Starcraft doesn't lock object movement on the grid; a ship can move from any point A to any point B. The reason it looks smooth is because they've rendered many possible directions of the sprite:
http://imgur.com/FAx3Q

Then they simply decide, depending on the angle of direction, which sprite to draw.

If you're drawing each sprite by hand, you can get away with far fewer directions. Alternatively, you could render your sprites with a top-down look (e.g. GTA2 style), so that you only need one sprite per character, rotated to the direction. But that might not flow with your game's perspective.

I ran into something a few days ago that might answer your question. If you really want a free-form path finding algorithm, and are unafraid to write some code, you can make polygon based path-finding. I have never implemented it, but it is the algorithm style used in games like Halo2 (and three, etc.) and Left4Dead. A good one can procedurally generate a set of polygons that the player can travel across, compensate for the width of the player when rounding corners, and update based on dynamic obstructions.

See the following:
http://www.ai-blog.net/archives/000152.html
http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt

Implemented in Left4Dead:
http://www.youtube.com/watch?v=9lGCulh5_Ls

_________________
"Artificial intelligence will never be a match for human stupidity" - "Jamos Kennedynos"

Have you tried looking at pathfinding with waypoints/nodes?

I'm not sure how it could be handled in 2D but i know in 3D that nav meshes are used quite a bit too

Alright here's how I would do it.

I would make a grid in which I place all the immovable objects, such as buildings, trees etc.

Units are not restricted by the grid.

Units ignores other units when searching for a path.

To prevent units from "hugging" eachother when walking in opposite directions, I would probably make the unit move at a slightly different angle or something similar, when it collides with another unit.

This is how I would do it. Definitly not perfect and unit would probably block each other every now and then. Should be pretty easy to implement though.

2d nav meshes seems to be perfect solution, but... tiles for most simple games is best for now

_________________
Blog | Last game Gravity Duck tribute | In progress Gravity Duck tribute

Owh god, i started something hard!
Hmm, nav meshes seems to be quite hard to program, and especially a lot of work.
I like your thinking Epicbo, ill try something along those lines.

What advantage would a nav meshe have over a* in 2d games? Ive looked some vids and read some info about it. It seems to be that nav meshes take more efficient routes, and will get stuck less often because of that. What else?

Thanks for all the valuable posts here!