2

I have an XNA zombie survival game, where the player has to hold out in a building and zombies come at them by waves. Zombies initially target barricades to get to the player, and then target the player once they break down the barricade.

Here is an image of the game so far. Walls (indestructible) are in black/grey, barricades are in brown:

UPDATE: I have made a lot of progress so far in my understanding of pathfinding, but still no dice. The above picture shows my current grid/node system.

As you can see, outside the "arena" there are very few waypoints. The zombies need to get to their nearest waypoint on a road, so they can then head towards the barrier (the top road still needs a barrier, I know).

Once they break down the barriers they need to use pathfinding to find and follow the player around walls and obstacles, so there are a lot more waypoints.

I am currently storing each of the grid points in a Microsoft.XNA.Framework.Point array. I have tried so hard to implement this with this article which I have referenced so much, but my system and his are completely different and I can't find a way of making it work. For example, the article's system looks one grid unit in each direction to look for a node neighbour. Seeing as the waypoints outside the arenas don't have node neighbours right next to them, the system fails.

XNA is a dying framework and there is no usable articles/tutorials on pathfinding so I really need some help here.

Frayt
  • 1,194
  • 2
  • 17
  • 38
  • 2
    A* is probably still the way to go. Easiest is to add your own waypoints at specific locations (e.g. the middle of the doors, corner of the walls), rather than try to process every pixel though. – steve cook May 02 '15 at 18:45
  • 1
    possible duplicate of [Simplest implementation of A\* algorithm?](http://stackoverflow.com/questions/2138642/simplest-implementation-of-a-algorithm) – steve cook May 02 '15 at 18:48
  • _"but that is based around a **grid system** and my game is based around rectangles"_ - Incorrect. _[Rather than being concretely tied to a square grid, such as a chess board, or a hexagonal grid like seen in Chinese checkers, the A* algorithm is only concerned about nodes, their neighbors, and how far away each neighbor is](http://stevephillips.me/blog/implementing-pathfinding-algorithm-xna)_ –  May 03 '15 at 01:20
  • If you want "simple" you can try http://www.red3d.com/cwr/steer/ however you may find that Steering Behaviours is only useful for immediate obstacles and not complex long-term goals such as move around a wall; enter a door; move across two rooms; finding a door in the process. And forget about stairs. A* will do **all** those things. Steering does have **path following** but then you need to work out a dynamic path sadly –  May 03 '15 at 01:34

1 Answers1

3

With an a* style pathfinding algorithm, a grid based game level is ideal, as an array of data provides the a* algorithm with what it needs to determine an optimal path.

When you move away from grid-based games, you need to get a little more clever. Your best option is to create a node based a* pathfinder. This implementation requires you to define "nodes" in your level, that serve as waypoints, in a path. Your algorithm utilizes the pre-defined nodes, in a modified a* implementation, to determine the optimal path.

You can even generate these waypoint nodes programatically based on your level. I wrote an implementation in unity described here .

Beyond this, you can look into Navigation Meshes. This technique involves calculating or pre-defining polygons in your level that allow movement. This is a bit more involved, but produces much better results.

jgallant
  • 11,143
  • 1
  • 38
  • 72
  • @Frayt The author describes under **Setting Up the Node Tree**. Refer to _"that I discussed in my last post on sandbagging "_ –  May 03 '15 at 10:02
  • I have updated the question with my progress, if you could both take a look that would be excellent. – Frayt May 03 '15 at 22:40