How to path-find in a non-tiled world?

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
togFox
Party member
Posts: 112
Joined: Sat Jan 30, 2021 9:46 am

How to path-find in a non-tiled world?

Post by togFox »

I have a top down 2D sports field with players running about in a pixel like way - like the whole Cartesian x/y plane is used. They don't follow tiles.

The soccer player (AI) needs to get from his/her half to the opposing goal by finding a path that best avoids the opposing team. All the libraries I've seen use a tile map and go from there.

In the absence of other techniques, I'm thinking of virtually dividing the playing field into tiles where a tile with an opposing player being a 'wall' that needs to be avoided. I can adjust and tune the size of the virtual tiles through experimenting or even in real time depending on how/where the players move. I can refresh the virtual map once per dt (or whatever).

Another option is something I'd need to research where some sort of 'density' analysis determines where there are more players ( to avoid) or less players (more viable).

Where should I start?
User avatar
Xii
Citizen
Posts: 81
Joined: Thu Aug 13, 2020 9:09 pm
Contact:

Re: How to path-find in a non-tiled world?

Post by Xii »

If the number of entities isn't too high, what you can do is consider the distances and directions (vectors, essentially) towards each and every other entity.

Begin with a vector pointing straight to the goal, or something. Then, loop over all opponents. Subtract from the initial vector the vector towards each opponent, weighted by the inverse square of the distance to said opponent. Then have the entity move towards the final resulting vector. This creates avoidance behavior in real-time.
dusoft
Party member
Posts: 127
Joined: Fri Nov 08, 2013 12:07 am

Re: How to path-find in a non-tiled world?

Post by dusoft »

A* / A star? Pixels are basically tiles or tiles are represented in the same way as pixels - by their X,Y position.

Pixels/tiles taken by opposing players are basically just blockers/walls.
togFox
Party member
Posts: 112
Joined: Sat Jan 30, 2021 9:46 am

Re: How to path-find in a non-tiled world?

Post by togFox »

oh - that vector method is not something I've seen before and this project has made me very comfortable with vectors.

The A* method would give a poor result because my 'grid' is 100 pixels by 53 pixels. That's 5300 pixels with only 11 pixels occupied. The vector method would demonstrate avoidance in a way that A* would not.

Thanks both. More learning to do.
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 24 guests