# How can I “smoothen” my path-finding on a map with big tiles?

I've just implemented A* in my "game", but as I finished it this came to my mind:

• This is fine for a turn based game, but it would be really annoying for a real-time one.

For example look at the picture below.

In an action rpg the character would move to its goal in a straight line, but this is impossible here because the tiles are too big to make a that straight line.

So my question is:

• How do they solve this in action games?

• (I don't think that they have miniature tiles because that's too inefficient. But maybe I'm wrong.)

Edit:

• Or should I remove those tiles from path, which aren't necessary?

• So there will be a only a few points left, which are connected by straight lines?
• Like this: go through the path from the Start.

• When I find a X. tile which can't be accessed with a straight line from start:

• Remove every tile from the path between Start and (X - 1). tile.

• Repeat this from the X. tile, till I find the End.

• Interpolate through straight lines between the remaining points.

The tiles will be used for graphics and for obstacles, but not for navigation.

For navigation, i.e. moving from point A to point B, you'll use something like a navmesh, or a navigation mesh.

Basically, all of the points of interest of the surface where the agent will be able to travel will be used to create a graph, graph nodes will be composed of the points of interest, and graph edges will be composed of direct paths between points of interest. This means that the graph will 'surround' obstacles.

With that graph, an agent can find the closest point of interest from its current location, and then use A* to find the shortest path to where they like.

That's the big picture. You can browse this site for more questions tagged , and if you're interested in navmeshes in Unity, you can browse this site for questions about it. From what I understand, there is a built-in feature about navmeshes in Unity, but I don't know anything about it.

• Yes, navmesh would be the perfect for me. Unity's is not good for me, because my maps are dynamic. I searched for nav mesh generation, but I couldn't understand how could I make polygons from the walkable areas and then how could something find the shortest path in a polygon. – Tudvari Jan 30 '17 at 15:34

In an action game they would not be using tiles, as it's likely there are not restrictions to the directions characters can move, so although they may be in a diagonal like yours they would rotate towards it and move straight at the goal. They would not necessarily use an A* style algorithm but rather just target seeking. Path finding would be implemented if there were obstacles in the way however. A* could be used for that since it is good at finding the best path.

For a turn based game it is totally okay to do something like this with tiles. If you are concerned with the fact that your cube character would have to go up and then right instead of up-right diagonally then try implementing diagonal movement in. While it may not look like a straight line the character would still be heading in that path straight to the goal.

Check this article out. It was my primary reading for a course where the final project was about flocking, target seeking, autonomous agents etc.

• What do you mean by target seeking? I know what does that mean, but I don't know what can I implement it efficiently in a dynamic environment. – Tudvari Jan 30 '17 at 15:30
• In the past when I have used target seeking it is having your position, and having the target position and you actively add forces (seeking etc) towards that location. You can have weights that impact various things, such as if there is an obstacle, it forces the character away from it during it's path, if there was an enemy it would run away. That's probably not the best explanation of what I mean but I am going to edit my post with a link to a really good article. – n_plum Jan 30 '17 at 15:44

I think what you're looking for is Bezier Curves. I'm not exactly sure about how your game does what it needs to do (or what you intend to do with the tiles), but if you have points (tile coordinates) and you want a smooth transition between them, Bezier Curves will give that to you as a path. The rest is just animation and moving the character model along the path.

If you implement it right, you would get something like this: