Theres must be a way of doing this more effectively!

p5.js Coding Questions
1

Hi all,

At the moment I have a tile based system and I want to move either North, East, South or West of a tile, depending on what tile the ‘player’ is in. Done this fine. However my problems comes because of walls in the tile system. I have programmed A* to take me round the map and avoid the walls. However if I click and the tile is against a wall, A* freaks out because the verification is before running A*.

Red = ‘Player’
Blue = ‘Enemy’
LightBlue = ‘CourserPos’

image

What i need is to analyse the tiles around. So if my test is the north tile, like north round to west clockwise, if my test is the east tile, look east round to north for all four cases.

image image image image

I have been stuck on this one for a while now for a smart solution. I am able to code everything manually and this is loads of lines that must have smart solution, however I want a way that loops in some way.

var neibours = this.returnValidNeibours(this.Mapx, this.Mapy);
          //[north,east,south,west] t or f
          if (yTile < this.Mapy) { //north
            //var neiboursSub = neibours.slice(0, 4); ???
            var pos = createVector(this.Mapx, this.Mapy-1);
            return pos
          }
          if (xTile > this.Mapx) { //east
            var pos = createVector(this.Mapx+1, this.Mapy);
            return pos
          }
          if (yTile > this.Mapy) {//south
            var pos = createVector(this.Mapx, this.Mapy+1);
            return pos
          }
          if (xTile < this.Mapx) { //west
            var pos = createVector(this.Mapx-1, this.Mapy);
            return pos
          }

The above code is the section where it decides what case to try. x/yTile is the player, and this.Mapx/y is the ‘enemy’ Objects position. I need some sort of algorithm or method to test these effectively? I have thought about using arr.splice on an array that is longer eg repeats to get the 4 tests i need in the right place.

Cant figure a smart solution out on this one.

Thanks for advance for taking time to read this and offering any ideas!

EDIT: Im not looking for the code itself, just a idea or an example that I having thought of, or that I’ll just have to go long way around and there isn’t a way…

Peachman.

1 Like
2

For small enough worlds or short enough pathing distances, A* is an overkill over a much simpler breadth-first search since it’s much easier and faster to code and run a simple queue than to implement a priority queue that supports arbitrary insertions.

How you might optimize this depends on the way your world is implemented. For instance, for a bounded size grid, I would forego using 2D arrays and just use a flat array indexed as world[ j*nWide+i ].

Rather than your createVector(), you could just think in terms of a single integer direction variable. From a given grid cell with index “idx”, your neighbor in direction “dir” could be idx+next[dir] where next is a simple array of { 1, nWide, -1, -nWide }. You do have to worry about the edges of the world, however, but maybe you put walls around the edges to prevent the players or the pathing algorithm from stepping off the sides.

You can find the integer direction between the player and enemies with a little trig:
dir = (atan2( dy, dx ) * 4 / TAU + 4) % 4
or something like that.

5 Likes
3

Another optimization you might consider would be for each cell to have a bit-field with one bit for each direction that is 0 if you can’t go to that neighbor cell or 1 if you can. So you can move in direction “dir” only if ( (paths[idx] & (1 << dir )) > 0 ). Saves querying each neighbor unless you have a path to them.

If something opens or closes a door or punches a hole in a wall, just xor the right bits in the neighboring cells and the pathing will take it into account.

4 Likes
4

Hi Scudly, thanks for the reply!

Firstly I knew A* was over kill, this was just something I’ve always wanted to get working, I’ve not really investigated into other path finding methods, but will do for future project.

Something I also didn’t mention was I’m using the tiled library for p5.js, as the base of the tile system (hence why the createVecors). I have been able to work on top of this as like an ‘overlay’ layer as such. I did think about putting a 1D array grid on top of the tilemap to contain data and work from that instead.

I think I understand the concepts you have mentions and will try to give this a go and implement a system to try and solve my problem!

Thanks again!

Peachman