Pathfinding

[Jeremy-Barnes]

Old Greywater Alpha Pathfinding is quite expensive. Though the framework doesn't yet support moving/pathfinding, begin looking at making pathfinding more efficient

[Biodiscus]

I think the best algorithm is potential field, http://aigamedev.com/open/tutorials/potential-fields/

[Jeremy-Barnes]

That will probably work well for enemy movement, but we will still need A* for player-pathing (finding the best path from where the player is currently to where they clicked to move to).

[Biodiscus]

I will implement them both

[Jeremy-Barnes]

I saw you've got a version up on your personal repo, are you gonna put that in soon?

[Biodiscus]

Yes, not today but tommorow I will implement potential fields tommorow, when that's done I will commit it to the Greywater Repo. (If you need the A* now, tell me and I will commit it)

[Jeremy-Barnes]

If you'd get the A* working in our system today or tomorrow, that would be helpful. Isometric rendering is basically done so I'm going to start hooking up Tavish's movement once that's in place.

[Jeremy-Barnes]

New issues with A*:

It doesn't seem able to find diagonal paths - going from 2,3 to 3,4 follows this path: 2,3 2,4 3,4

This is obviously silly, when the shortest path is to move diagonally from 2,3 to 3,4. This is a pretty big deal.

Also, it doesn't seem to be able to find its way back: Going from 3,4 to 2,3 finds no path at all.

I think this is because the generateSuccessor method only expands up and to the right. I'm not sure why that is:

if (y < map.length - 1 && map[y + 1][x] != 1)
        ret.add(new Point(x, y + 1));
if (x < map[0].length - 1 && map[y][x + 1] != 1)
        ret.add(new Point(x + 1, y));

There are 8 potential directions, and players might very well want to move down and left. Whats going on here? I must be misunderstanding something.

[Biodiscus]

Hmmm, I will fix it after my math lessons today (6 gmt+1)

[Biodiscus]

I've fixed the 8 direction, but it doesn't behave properly:

[Jeremy-Barnes]

What am I looking at? Is red the path?

[Biodiscus]

Yellow is :(

[Jeremy-Barnes]

Okay, so blue and green are start/end, and red is obstacles?

[Jeremy-Barnes]

Hmm, I tested the new version and its doing better, but still a little weird. I tested it on a 10x10 open grid (no obstacles) and told it to go from 2,3 to 9,3 (straight line) and it gave me 2,3 3,3 4,3, 5,3 6,3 7,3 8,2 9,3

I'm going to tinker with this a bit, hows potential field coming?

[Jeremy-Barnes]

I'll be committing my pathfinder integration here pretty soon, there are a few changes I'd like to see to make life a bit easier all around (just do these in your next commit):

Make pathfinder an abstract class, make an AStar class and PotentialField class that extend it. There are a handful of utility methods that both will need that I've put into Pathfinder. Also, the Mob will have a Pathfinder and that can be either A* or PF, that superclass thing will make that possible.

Swap the orientation of the int[][] array - I know the tradition is to do [y][x], but that is the opposite of the convention used everywhere else on earth (points are x,y, squares are width,height, etc etc). The Level class is oriented [x][y] so when I test right now the paths it gives are crazy.

Thanks!

[Jeremy-Barnes]

Added logic for pathfinding to Player class - doesn't function yet, I have to do a bit more work for that, but it is basically done and should give you a very clear picture of how Mobs will work with the pathfinder.

Also, the pathfinder won't work on tavish until our int[][] standards match up (see above comment)

[Jeremy-Barnes]

Robin Robin Robin Robin!

Big Deal Please Fix Soon!

Potential Field doesn't work in game. It looks like the primary issues are to do with curPos and the nodesDirections in PathFinderMotor. Looking at the call hierarchy for both, they are never declared, which makes sense, they keep throwing up null references for me.

I will use A* for the Watchman for tonight, but PF is currently borked :(

[Jeremy-Barnes]

So, just fixed the A* bug myself, it was this:

            if (x < map.length - 1 && y > 0 && map[x + 1][y +1] != 1)
                ret.add(new Point(x + 1, y - 1)); // Down-Right

Look very carefully at the if and the add statements

The Potential Field is still broken. I won't be working on that, I'm trying to get the sound and attacking working, I just need some pathfinding to test that, A* works fine for testing.

More important bug reports from the field -

There are some slight issues with bounds checking in the A* generate successor method.

When I stand at 0,99 (the corner), line 76 crashes out -

if (x < map.length - 1 && y > 0 && map[x + 1][y + 1] != 1)

The boundary limit of y>0 catches people walking off the left side of the map, but it doesn't catch people walking off the right side of the map. Even though I was trying to walk towards the center, it still expanded that node which is greater than the size of the array.

The max Y is 99, it tried to expand 100 and the if statements currently don't handle that behavior.

Please fix before Potential Field. It should be an easy fix.

You can move Tavish around as needed to test, as well. Just put him in a corner (0,0) (99,0) (0,99) (99,99) and try walking.

You can change Tav's start location in the constructor for level

TestTavishMob = new Player(0,99, this);