CODEWITHSUNDEEP
algorithmpath-findinga-star
orom
orom

Reputation: 861

A* map segmentation algorithms

I am working on a game where player can move in arbitrary directions. The map consists of obstacles placed at arbitrary locations and of different size. All obstacles/objects are of rectangular shape.

So far I've implement a basic A* algorithm (8 directions of movement) using simple two dimensional grid where each cell in a grid refers to a single pixel on the map. Obviously it doesn't work well especially for large 2000x2000ish or so maps. Please note that I can't use data structures other than a 2-dimensional grid due to some external constrains.

Before I jump into JPS, swamps and other fancy stuff. I figured I should try a different approach for 'segmenting' the map into movement points. That is, instead of 1 cell <-> 1 pixel mapping do maybe 1 cell <-> 5x5 pixel wide area in the map.

However I can't seem to figure a proper way to do this. Since player size can change and due to arbitrary placement of obstacles I am running into all sort of clearance issues.

So my question is: how to efficiently 'segment' a map into a 2-dim grid to be used by A* given the above constrains?

Upvotes: 2

Views: 311

Answers (1)

TJ27
TJ27

Reputation: 308

You can create a navmesh on your map, see e.g. AI Game Programming Wisdom - there is a big chunk of that on Google books too (google e.g., "construct navmesh").

Another option (if you do not want to restrict yourself to navmesh) is to use something like quad tree navigation.

Upvotes: 1

Related Questions