2
\$\begingroup\$

The enemies in my game are supposed to follow the player in order to cause damage to it. Right now, I have it where the enemy just goes in the direction that will bring it closer to the player, and this works fine, but the enemy gets caught on obstacles and solid tiles. The Collision.tileCollision methods check to see if there is or will be a collision with any solid tiles, by adding the speed of the enemy to its current coordinate, in order to look ahead for collisions. If there is no collision, and the direction its checking will bring the enemy closer to the player, then it goes in that direction.

if (Collision.tileCollisionRight(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel) 
    == false && (Math.abs((this.thisEnemy.getX() + this.thisEnemy.getSpeed()) 
    - this.player.getX()) < Collision.getXDist(this.thisEnemy, this.player)))
{
    //Should/Can go right
    this.thisEnemy.setX(this.thisEnemy.getX() + this.thisEnemy.getSpeed());
}
else if (Collision.tileCollisionLeft(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel)
    == false && (Math.abs((this.thisEnemy.getX() - this.thisEnemy.getSpeed()) 
    - this.player.getX())) < Collision.getXDist(this.thisEnemy, this.player))
{
    //Should/Can go left
    this.thisEnemy.setX(this.thisEnemy.getX() - this.thisEnemy.getSpeed());
}

if (Collision.tileCollisionDown(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel) 
    == false && (Math.abs((this.thisEnemy.getY() + this.thisEnemy.getSpeed()) 
    - this.player.getY()) < Collision.getYDist(this.thisEnemy, this.player)))
{
    //Should/Can go down
    this.thisEnemy.setY(this.thisEnemy.getY() + this.thisEnemy.getSpeed());
}
else if (Collision.tileCollisionUp(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel) 
    == false && (Math.abs((this.thisEnemy.getY() - this.thisEnemy.getSpeed()) 
    - this.player.getY()) < Collision.getYDist(this.thisEnemy, this.player)))
{
    //Should/Can go up
    this.thisEnemy.setY(this.thisEnemy.getY() - this.thisEnemy.getSpeed());
}

I have heard that the A* search algorithm is good for path finding, but I have no idea how to implement the algorithm into my program in order for the enemies to not get stuck on walls when following the player. How would I go about doing such a thing? My program is tiles based for obstacles such as walls, but entities like the player and enemies have free movement. This is where I'm confused; I understand how it would work, if the entities also did tile based movements, but that is not how my game is set up. I don't want to check every pixel on the screen for a path, because that would take forever, and be extremely inefficient.

\$\endgroup\$
  • \$\begingroup\$ The player has free movement but he is always inside some tile(s). Use A* to get a path to the tile where the player is (or most of it is), and move to each tile using your current approach (except that collision detection is not necessary), but having a tile as a target (you may use its center coordinates). If the enemy is already in the same tile, simply use your current approach. \$\endgroup\$ – rcpinto Jul 3 '16 at 23:46
  • 1
    \$\begingroup\$ Wikipedia has a great rundown of how to implement A*, the only modification I made was using a Node Object, instead of storing the weights in Maps. \$\endgroup\$ – Shaun Wild Jul 4 '16 at 11:53
  • \$\begingroup\$ policyalmanac.org/games/aStarTutorial.htm This one helped me. Don't hard code A* into your characters logic but rather let them or some AI/System request a path to follow. \$\endgroup\$ – Sidar Jun 14 '17 at 1:03
  • \$\begingroup\$ If you use A* for every bot, your performance will be much worse than to run Dijkstra just once out from the player to each bot. As you reach each bot it can immediately be assigined a next move, and the algorithm continues outwards until al bots have been assigned a next move. Since both algorithms actually run best backwards (ie from destination to source) this is a particularly fitting AND efficient approach. \$\endgroup\$ – Pieter Geerkens Jun 14 '17 at 2:34
1
\$\begingroup\$

A* works on graphs, and graphs are discrete nodes and edges. Free movement isn't discrete, so you'll need to come up with a map representation. Read this article by amitp which explains everything in great detail.

You need to choose a type of representation, and each has pros and cons. If you're going for shortest path, the obvious answer is a polygonal graph like this:

polygonal graph

That is, for each obstacle, create nodes out of each corner of each obstacle, create start and end nodes, and connect everything up based on visibility. The shortest (Euclidean) path is guaranteed to be within this graph.

The problem is that such graphs can become very complex, as you can have lots of nodes connected to each other:

polygonal graph complex

This is why lots of real games use other approaches, like manually placing waypoints, or navigation meshes. Grid-based ones are fine too. Also consider hybrid approaches. For example, in one of my games, everything is tile-based but movement is (almost) free. I use A* over the tile grid, but then smooth out the paths by removing nodes in between if they are visible to each other. This allows the AI to move diagonally when following the path.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.