search

Warzone2100 / warzone2100

Command the forces of The Project in a battle to rebuild the world after mankind has been nearly destroyed by nuclear missiles. A 100% free and open source real-time strategy game for Windows, macOS, Linux, BSD+
https://wz2100.net
GNU General Public License v2.0
3.13k stars 518 forks source link

Improve the pathfinding engine #873

Open cpdef opened 4 years ago

cpdef commented 4 years ago

Describe the feature you'd like first general ideas from people on discord:

  1. At moment we use the A* algorithm. It could be replaced for bigger maps with the flow-field algorithm
  2. Droids should be able to avoid enemy units, like if they are ordered back for repair

now two of my ideas:

  1. Maybe the path should be editable by wzapi bots.
  2. remake the pathfinding code (its ugly :) like it contains goto statements etc.)

Describe why do you think it is needed

  1. if we want to have maps with bigger size, A* might have to slow performance
  2. to improve the gameplay
  3. To let bots define their own path for special operations, like a formation of the tanks or so
KJeff01 commented 4 years ago

It shouldn't depend on map size since all maps can suffer from pathing issues.

There has been some progress on a flowfield implementation in this branch plus a cleanup. It's not finished, or free of issues, but most of the work is done.

cpdef commented 4 years ago

Ok didn't know somebody worked on it already. But the last commit seems to be very long ago, so we would have to check, which parts of it can be used. I'll look into that.

It shouldn't depend on map size since all maps can suffer from pathing issues.

didn't got that one? Doesn't every algorithm take more time for bigger sized maps?

bjorn-ali-goransson commented 4 years ago

What @KJeff01 means is that If the new algorithm is better, then it should be enabled regardless of map size.

bjorn-ali-goransson commented 4 years ago

I researched this a bit yesterday, and Perl99:s PR is essentially what we should do. It's also exactly the same algorithm as this book (as Perl99 states himself):

  1. Split the map into flow-fieldable "segments" (for performance)
  2. Mark openings ("portals") between segments
  3. Setup "cost" (of traversing) for each tile.

Then, for each path that needs to be calculated, if the unit and the target are in the same segment, that segments flow field is generated.

If they are not in the same segment, a traditional A* path is construed BETWEEN PORTALS. This decides what segments the unit will traverse to reach its goal. It also means that "the flow field for reaching portal A from portal B in the same segment" is cacheable.

Well that's the theory of it, the code seems to be doing this, but perhaps I can try to understand exactly what's going on as it seemed to be misbehaving when the team tried it out.

@cpdef do you want to take this on? I could do this initial test (and merge from master as well) and return here with the results if you want.

cpdef commented 4 years ago

Can you make the initial test and then if you finished it the person, which has time and wants to do it can start it? I have at moment a few other things to do, but maybe i finished them until then?

bjorn-ali-goransson commented 4 years ago

I just looked through the cleanup branch and it's purely cosmetical, I believe those kinds of PRs should be merged only when fresh.

Furthermore it's not related to the pathfinding at all, only some movement logic. Can we disregard it in this issue?

bjorn-ali-goransson commented 4 years ago

@cpdef absolutely

bjorn-ali-goransson commented 3 years ago

I'm working on this in https://github.com/bjorn-ali-goransson/warzone2100/tree/bjorn-ali-goransson/flowfield-pathfinding