Jump to content
  • Advertisement
Sign in to follow this  
menyo

line based pathfinding?

This topic is 2474 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

pathfinding.jpg

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!