1
\$\begingroup\$

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.

Path

\$\endgroup\$
1

4 Answers 4

Reset to default
1
\$\begingroup\$

Since your question is quite broad (you don't seem to have an actual issue to solve), I'll write a broad answer.

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 30, 2017 at 15:34
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 30, 2017 at 15:30
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 30, 2017 at 15:44
1
\$\begingroup\$

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: enter image description here

More info on the math involved and also some code.

Most likely path to be generated in this particular case: enter image description here

\$\endgroup\$
8
  • \$\begingroup\$ I thought about this too but the problem is that the character's visual representation could be annoyingly far away from its actual position. (Which is bad for example when the player wants to dodge projectiles) \$\endgroup\$ Commented Jan 30, 2017 at 15:29
  • \$\begingroup\$ You could just interrupt movement if a new order is given, so if you're using mouse to direct the character and you have a pathfinding algorithm, you can re-calculate every frame (or every few frames for performance reasons if necessary). It would just mean interrupting the characters path, then making a new path. Of course, you'd need to handle continuous animation (something like, start animation on mousedown, stop animation when the character stops moving). Also, the positioning is really down to how much weight you're giving each dot on the curve, see the bottom part of the second link. \$\endgroup\$ Commented Jan 30, 2017 at 15:40
  • \$\begingroup\$ Yes, but visually approximating the path could be misleading. I could set the weights to lower the chance of highly misinformating graphical position, but that wouldn't be enough. It would be really frustrating for the player for example if he wants to dodge a trap, and visually he indeed dodges it, but its real position triggers the trap. \$\endgroup\$ Commented Jan 30, 2017 at 16:09
  • \$\begingroup\$ With tiles that big, the player character won't be so off-base. I've added another picture to show the most likely curve that path will take. You could also just make a bezier curve every 3 tiles so that it never goes so off base that it'll be misleading. \$\endgroup\$ Commented Jan 30, 2017 at 16:14
  • \$\begingroup\$ Oh, you misunderstood me. Yes, this would make the path smoother, but I didn't mean this by "smoothen". What I meant: In this example, the character could just straightly go to its target position (in a straight line) but he can't because the grid only lets K * 45 degree directions. (8 directions) \$\endgroup\$ Commented Jan 30, 2017 at 16:21
-2
\$\begingroup\$

In the image given, it looks like you can move in a straight line: just find the line between the two points and move along that. That would mean that the position couldn't just be 0,1,2..., but it would have to be interpolated in between.

\$\endgroup\$
2
  • \$\begingroup\$ Currently it interpolates between the tiles found by the algorhytm. But if I just interpolate between the start and the end point, then what's the point of the node based path-finding? \$\endgroup\$ Commented Jan 29, 2017 at 22:53
  • \$\begingroup\$ Ok, so there are multiple "solutions" here. One is, as you already suggested, making the tiles smaller, although they would have to be really tiny for the path to appear straight. Another "solution" is to abandon tiles altogether. Tile based games have kinda gone out of fashion. One thing I would try is to make your algorithm prefer changing direction more often. In your image, the path goes down a bunch, then diagonal a bunch. It might look straighter if it went down-diagonal-down-diagonal. \$\endgroup\$ Commented Jan 30, 2017 at 4:46

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.