Pathfinding with AABB collision detection

I am not sure what way to go, so I’ll give you a quick overview on what is working and what is the goal.

I have a simple 2D Map. On this map there are several objectes (technically rectangles) that player and enemies collide with.
Pseudocode:
` If(enemy.BoundingBox.Intersects(collisionObject)) handleCollision();`

Collision handling is by now basically just to set the movement vector to zero before the movement actually takes place.

Once the player is too close to an enemy, the enemy starts chasing the player (to a certain range) which is a straight line (start position -> current player position).
So far so good.

The thing is, if the player runs behind - lets say a wall - the chasing enemy of course stops at the wall.

What approach should I take to tackle this issue? I need to calculate a path that considers all colliding rectangles on his way and avoids them.

Hey Wirago!

Nice project. You could do a thousand things.
This could help you with collision detection for large number of actors (https://github.com/UnterrainerInformatik/collisiongrid).

You could, for instance, ‘remember’ the last time you saw your enemy (because now you don’t because the wall blocks your sight) and let the enemy go to that point.
You’d need a collision-detection for the ‘scanline’ in order to detect if the sight is blocked.
Just an example.

The second thing you could do, is to grab some A* implementation and NOT tell your enemy to go in the direction of the hero, but tell the A* algorithm to calculate the waypoints towards the hero’s position and let it follow that path.
Of course that’s very expensive and you would only trigger it once in a while and not on every update, but it’s a start.

My issue is that A* works on a grid based map.
Since my map is tile-based it actually is more or less grid based, but I do not have any information which tile is walkable and which not (at least not yet)
Why? Because my collision objects cover several tiles, sometimes only half a tile and so on.

Maybe I should - on level initialisation - build up this grid (check for each tile if it is covered by an collision rectangle) and implement A* based on this grid? The biggest map now is 100x100 tiles, so checking the collision status on load should not be a big issue.

Am I on a proper way with this thinking?

Oh. I have the luxury of making an RTS and the map is tile-based. Meaning you can walk on the whole tile or not.
If you don’t have that luxury, you have several ways to go.
You could do it the way you said yourself. Of course that works only if the obstacles are far enough apart to not have the pathfinding-map block an important way completely… But it should work.
You could go down that path here: https://gamedev.stackexchange.com/questions/58963/pathfinding-with-2d-non-grid-based-movement-over-uniform-terrain by creating a non-uniform mesh (there are path-finding algorithms for those as well).
You can look for some papers/links on my link-list here https://github.com/UnterrainerInformatik/GameDevelopmentLinks. I think I have linked a damn good A* library that does a fantastic job.

If you decide to go your way, the collisiongrid I linked in the last post can help you doing that (in fact it does exactly that by allowing to set arbitrary rectangles and it records the hit tiles…)
That would, of course, only work really well if your obstacles were axis-aligned…
Just let me know if you’re in need of further assistance.

1 Like

If you can treat it like a 2d tilemap and do pathfinding based on tiles, I have this code here:

Basically its based on some other dude’s Unity code but I made couple of improvements and separated it from Unity scene it was bound to. Its for Unity but since its C# you can easily use it for MonoGame.

There’s a link there to the original tutorial its based on, if you want to learn more.

Hope this helps.

2 Likes

Thank you guys, that helped a lot!

1 Like