# How do I make AI avoiding obstacles on tile map?

I implemented 2 NPCs chasing the character using Dijkstra algorithm for pathfinding. Tile map is represented by graph, where a node is basically the tile, and the adjacency list consist of adjacent tiles.

Only walkable way points are added to the graph (tiles which are not empty on walkable layers). All obstacles and their backgrounds are on different layers, that are not used for path finding. However, you can see that entities do intersect obstacles or end up on non-walkable layers).

How would experienced game developer handle this? What strategy should I use? I have tried applying collider which I use for my character to avoid intersection of obstacles to the NPCs, however this results in chaotic velocity changes (AI applies velocity and collider drops it)

UPD:

I noticed that I was comparing entity's top left corner to tile center to check if entity has reached a certain tile.

Now i use tile's center and entity's center to check if the entity reaches certain tile while traversing the path. Diagonal movement to diagonally adjacent tiles is also possible. But it still does not solve the problem even though now movement is more natural.

private fun modifyVelocity(tileIndex: Int) {
val nextPos = tileMap.getTilePosition(tileIndex)
val x = nextPos.x + tileMap.getTileWidth() / 2
val y = nextPos.y + tileMap.getTileHeight() / 2

val centerPoint = params.getCenterPoint()

params.velocityX = when {
isHorizontalDiffInsignificant(x) -> 0f
x > centerPoint.x -> VELOCITY
x < centerPoint.x -> -VELOCITY
else -> 0f
}

params.velocityY = when {
isVerticalDiffInsignificant(y) -> 0f
y > centerPoint.y -> VELOCITY
y < centerPoint.y -> -VELOCITY
else -> 0f
}
}


I also can show the unwalkable layers of the map, which are not added to the path. One layer for obstacles and one layer for their background.

I personally have a feeling, that this is geometrical problem, probably I should use another point to represent entity position

• It looks to me in the animation like the character doesn't just "partly intersect" the obstacles like the sacks at the bottom of the screen - it walks right on top of them. So either you're not marking enough tiles non-walkable, or the point representing your characters' tile positions is not at all aligned with the visible location of their feet - like if they're pathing based on the top-left corner of their bounding box instead. It's difficult to judge the source of the problem from only this animation. Can you edit your question to explain in more detail, or include more diagnostic images? Apr 20, 2023 at 13:52
• @DMGregory I have updated my question and provided more data Apr 21, 2023 at 10:31
• @DMGregory I actually got the hint about feet location in your comment. Taking the feet center point as a point to compare with tile position made movement almost correct. I also removed the diagonal movement ability to prevent intersecting obstacles around the diagonal adjacent tile Apr 21, 2023 at 11:10

Since heights of tiles and entities may vary dramatically, the idea of comparing their centers is wrong way to solve this problem.

After some research I came up with a solution which supposes comparing bottom-center positions of the tiles and the entities.

    val nextPos = tileMap.getTilePosition(tileIndex)
val x = nextPos.x + tileMap.getTileWidth() / 2
val bottomY = nextPos.y + tileMap.getTileHeight()

val centerPoint = params.getCenterPoint().x
val bottomPoint = params.y + params.ySize

params.velocityX = when {
isHorizontalDiffInsignificant(x) -> 0f
x > centerPoint -> VELOCITY
x < centerPoint -> -VELOCITY
else -> 0f
}

params.velocityY = when {
isVerticalDiffInsignificant(bottomY) -> 0f
bottomY > bottomPoint -> VELOCITY
bottomY < bottomPoint -> -VELOCITY
else -> 0f
}