1
\$\begingroup\$

I'm trying to build my first game, a really simple RTS like Age of Empires but I have a question about pathfinding.

When do this kind of games usually do pathfinding?

I've read some games do a global pathfinding once at game start but I'm not sure if that will fit this kind of games.

Do they usually calculate pathfinding each time a game entity starts a new task and has to move?

How do they handle when a obstacle suddenly appears on the path? Do they re-calculate pathfinding on every step? Or do they check if the current path is clear on every step? Or they just walk the current path until they actually hit the unexpected obstacle?

Actually if you know a link to a source code of pathfinding on some RTS game I would really appreciate it.

Thanks in advance

Improve this question
\$\endgroup\$
1
1
\$\begingroup\$

There are many ways to make pathfinding work..

Given AoE as example you will likely:

  • build a path each time a unit should go somewhere
  • check every next step and if it is impassable (e.g. blocked by a house) - rebuild path
  • check every next step and if it is blocked by another unit - do a quick side-step around it or wait a bit for it to walk away (cos units are small and mobile)
  • maintain areas connectivity map, to quickly discard pathfinding between unconnected areas on the map
  • use hierarchical pathfinding if you plan to have large maps
  • maintain a heat map and let units prefer paths over less used areas
  • schedule pathfinding across several ticks (or even move to threads) if you plan to have massive amounts of units
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Thanks I didn't know the connectivity map, that was one of my main concerns, lots of pathfinding operations wasting resources to reach unreachable places. The heat map options sounds really interesting too... \$\endgroup\$ – A. Matías Quezada Aug 18 '16 at 11:59
  • \$\begingroup\$ Connectivity map is a great performance-saver if your maps have more than 2 areas (e.g. bodies of land separated by sea). Also take a look into Hierarchical Pathfinding, it touches on the similar subject. \$\endgroup\$ – Kromster Aug 18 '16 at 12:09
1
\$\begingroup\$

Well it depend upon the situation all thing you have stated above happen, it depend upon your game or project. if you do not want processing every time to get high frame rates you just do path finding few times or if your game environment is static you don't have to use path finding every time. if your environment is dynamic i.e object moves then you have to use path finding frequently or you can detect if there is an obstacle and then take another path and follow A* path later.

You can view this nice tutorial on A* pathfinding:-

https://www.youtube.com/watch?v=-L-WgKMFuhE&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW

watch the tutorials first and then you can use the below scripts that I have created watching the tutorial with minor tweaks https://www.dropbox.com/sh/6r5o8u8vmcwyscx/AACAoqEK33qweGmm8uxcu57Ja?dl=0

Improve this answer
\$\endgroup\$
2

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.