• Question

  • For once I have a question for gud programmers

So im making an enemy AI system, and I wanna know how to get an enemy to efficiently pathfind from point A to point B around several polygons with hopefully minimal lag. i've never dabbled in pathfinding before so I don't know much about where to start, but I have some ideas.

anyways there's some smart guys here like letti, adam, and varrience so if any of you could show me how to do this or even recommend a good tutorial i'd greatly appreciate it.

anyways the functions I have at my disposal are:
isInside(); - returns if a point is inside a given polygon(boolean)
toRenderAt(); - returns all the polygons to render at a given point(part of extremely optimized and fast chunk system)
fatRenderAt(); - toRenderAt but with an extended radius, for things like players which can take up multiple chunks
nearestPointOnLine(); - gives the nearest point on a line to another point
clearPath(); - returns if a straight line between two points runs through any polygons(boolean)

so yeah if you could show me more or less how to get my AIs to pathfind it would be greatly appreciated, just give me the gist of how it works and i'll fill in all the little stuff

Also before you yell at me just to find an online tutorial IVE TRIED but none of them are what i'm looking for

    tbh, i know how, but like im probably gonna get banned soon due to a post i made so.. yeah, sorry

      no, its because i revealed that im 12, and the age requirement is 13

      I mean Adam saw the post and you aint banned yet. I'm thinking about it, but unless I get some orders from the other staff, maybe you're fine for now.

      ackvonhuelio I have made something like this before, but this one seems to be a little more complicated than it.

      What worked for me was converting the player and the enemy/point of interest into a binary matrix, or x and y coordinates represented as an array of ones and zeroes. The top left-most value would represent the player, and the bottom right where it needs to go. Zeroes mean spaces that are empty, and ones mean spaces that are occupied, and you can't pass through them. For example:

      //Top left and bottom right represent the enemy and the player's positions.
//The rest of the data represent the environment in between them
var matrix = [    
    [1, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 1, 0, 0, 0, 1, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 1, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 1]
]
/*

result:
x       x
  x   x  
    x    
  x   x  
x       x
*/

      The more data you're able to include into this matrix will mean slower filtering times, however the pathfinding will be more exact. For the algorithm, I suggest looking at this StackOverflow answer. You can set the start and end points (probably 0,0 and the very end of the array) and get the exact path and moves to follow to get to it.

      So, in steps:
      1) Get the player's x and y coordinates and the AI's coordinates

      2) Using their coordinates, make a box of the environment and convert that into a binary array. 0 means pixels the AI can move to, and 1 would mean occupied pixels, such as the collision borders of objects or obstacles

      3) Set the start and end points and throw that into the algorithm

      4) wow you have the pathfinded path route

          Letti42
          idk if this will work as my game map consists of lots of polygons, as opposed to a grid, but thanks nonetheless.

              ackvonhuelio Thats why you convert it into an array. You have collisions set with said polygons, no? You use those as the obstacles in the grid. You’re only getting data between the enemies and the player.

                well... from as far as i know an a* algorithm should be the fastest, however if all the AI follow this path the difficulty won't be as high as you want it to be, so you'll probably have to make it able to generate multiple paths to possibly surround the player rather than just have it follow the player but for that I assume you'll probably have to up or down the path cost, also for polygons you can just allocate more hitboxes for them the more complicated collisions you try to perform the slower your game gets, especially if the AI is testing that collision constantly, just make a small enough grid out of the players hitboxes and jump the player into one of the grid positions

                well i tried the a* pathfinding and unfortunately it was just to laggy with dozens of players and hundreds of polygons, even with a chunk system.

                luckily, with a bit of effort, i made my own pathfinding system, which i will be showing off very soon

                anyways thanks for trying to help

                Chat