6 replies to this topic

[menyo]

Hi,

Are there any resources about finding the shortest path with straight lines instead of using tiles? I am still using a tile based system for my game but i want the player and mobs "detached" from the tiles. The image might illustrate things better.



The path will never get too long since the player can only click as far as the screen goes and it should not calculate past a wall if, let's say a door through it, is outside the screen. Mobs however should chase the player like this for let's say 2 or 3 screens away.

I am thinking of drawing a line between location and destination and where it crosses collidable object insert a waypoint there and move it around until. But since i can come up with many problems with this technique i honestly have no clear idea where i should start.

So if anyone has a good resource about this subject i'd love to dig into it.

[IADaveMark]

There are various methods for combining tiles into larger tiles with the edges at chokepoints. I don't have the time to look them up now. Just wanted to toss that out there.

[menyo]

Could you hit me up with some keywords then since pathfinding + line/vector doesn't give me much.

[JTippetts]

I've gotten good results by generating the path as a series of tiles, then iterating the path to find the furthest tile along the path that the agent can walk in a straight line to. The agent moves directly to that tile, and periodically as it continues to move I will look ahead to see if a new tile has opened up, and move toward that tile if so. This tends to always smooth out the jaggies of a tile-based path while still allowing you to use the simple tile-based pathing scheme. However, the path smoothing can add overhead that may be undesirable if you have many agents trying to move.

[Delpee]

Like JTippetts said, just keep checking for a node in the path which can be reached directly (straight line) and has the lowest cost of the directly reachable nodes. Make sure to check once in a while if the node is still reachable (directly) if you have moving inpenetrable though!

[Matheus Cansian]

I think this should help ;)
http://drpexe.com/20...vmesh-detailed/

Instead of using grid, you can use polygons to navigate through your map

[menyo]

I will fill these tiles eventually with 3D meshes but since, apart from an occasional larger fixed mesh, i use small meshes for each tile the use of polygons to navigate through the map would not be efficient i guess. But fill me in on your thoughts.

Anyway, i used my tile based A* to find the lines and apart from a occasional bug where a enemy or player moves through a impassable tile it's working good. I used JTippets method making a collision course to each path, upon finding a collision the next location should be the previous tile in the list. Since it was my first A* algorithm and was aimed on tiles only i am going to create it from scratch to make it more efficient.

You can see the result at the blog in my signature, thanks for helping out.