Pathing AI for Engineer

[Nesciosquid]

Probably something like A*, such that the Engineer takes a reasonable path to the building target.

Requires some way to specify a location that the Engineer should travel to, collision detection on the Engineer for movement and some notation for what objects are permeable for pathfinding.

[dgoswami]

I would like to work on this. I know the A* and Dijkstra's shortest path algorithms. I will start by implementing the algorithm on a generic graph (probably an adjacency list) first, then work on transforming the current map/world data structure into a graph format that can be fed into the algorithm. The resulting path (sequence of graph nodes) can be transformed back into map coordinates that describes the Engineer's path.

Someone else is probably better suited to instantiating the Engineer when the relevant UI event has been registered (in Tank Controller?), then calling the A* algorithm to obtain a sequence of coordinates to travel to in order to get to the destination, and finally setting up the animation sequence. However, if I am done with the A* implementation before anyone else gets to this, I can try to work on this too.

[Nesciosquid]

Awesome!

For now, it would probably be easiest to ignore collisions with Tanks and other moving objects, and focus on StationaryElements that are considered 'solid'.

That way, you can use World.getMapTIles() to get a list of all the Terrain and StationaryElement objects that are on the 'grid' of Tiles in the world. You could create a list of object types the Engineer is not allowed to pass through (water, deep water, any solid StationaryEntity) and use the integer values of the grid to figure out which Tiles are valid path nodes. You could then return a list of tile locations (x, y integer pairs) that represent waypoints that the Engineer should travel to, which would then be handled by a controller to set up animation and movement.

The Tile.getTerrain(), Tile.getStationaryEntity(), Tile.getGridX(), and Tile.getGridY() commands will likely be useful, here.

If you want to get really fancy, you could go so far as to grab the speed modifiers from objects in the tiles, which you could use to prioritize easily-traversed terrain (grass) over slower terrain (swamp, crater, rubble..)

-Aaron

On Wed, Apr 2, 2014 at 4:16 PM, dgoswami notifications@github.com wrote:

I would like to work on this. I know the A* and Dijkstra's shortest path algorithms. I will start by implementing the algorithm on a generic graph (probably an adjacency list) first, then work on transforming the current map/world data structure into a graph format that can be fed into the algorithm. The resulting path (sequence of graph nodes) can be transformed back into map coordinates that describes the Engineer's path.

Someone else is probably better suited to instantiating the Engineer when the relevant UI event has been registered (in Tank Controller?), then calling the A* algorithm to obtain a sequence of coordinates to travel to in order to get to the destination, and finally setting up the animation sequence. However, if I am done with the A* implementation before anyone else gets to this, I can try to work on this too.

Reply to this email directly or view it on GitHubhttps://github.com/BU-CS673/bubolo/issues/262#issuecomment-39378009 .

[ChristopherCanfield]

This is great, Debbie! Implementing A* can be a lot of fun, especially when we see it controlling things graphically. The ants in my AI ant simulation project last semester used A* to move around, for example, which was really cool to see.

We do currently have an adjacency graph (though not an adjacency list) that is returned by the World: the 2D array of tile data, which you can access by calling world.getMapTiles() (all controllers receive a reference to the world in their update method, and I assume that controllers will be used to call your A* implementation). It currently provides information about whether or not areas are passable, but the cost isn't yet implemented. Once the movement cost is available, you'll be able to pull it from there as well. So that can either be a starting point to generate whatever you want to use, or it could be used directly, depending on your preference.

If we had more time left, your work on this would also benefit the creation of Tank AI, which would be very cool!

On Wed, Apr 2, 2014 at 4:16 PM, dgoswami notifications@github.com wrote:

I would like to work on this. I know the A* and Dijkstra's shortest path algorithms. I will start by implementing the algorithm on a generic graph (probably an adjacency list) first, then work on transforming the current map/world data structure into a graph format that can be fed into the algorithm. The resulting path (sequence of graph nodes) can be transformed back into map coordinates that describes the Engineer's path.

Someone else is probably better suited to instantiating the Engineer when the relevant UI event has been registered (in Tank Controller?), then calling the A* algorithm to obtain a sequence of coordinates to travel to in order to get to the destination, and finally setting up the animation sequence. However, if I am done with the A* implementation before anyone else gets to this, I can try to work on this too.

Reply to this email directly or view it on GitHubhttps://github.com/BU-CS673/bubolo/issues/262#issuecomment-39378009 .

[ChristopherCanfield]

Aaron beat me to a few points :). That's the problem with quadruple checking everything...

On Wed, Apr 2, 2014 at 4:37 PM, Christopher Canfield cdcanfield@gmail.comwrote:

This is great, Debbie! Implementing A* can be a lot of fun, especially when we see it controlling things graphically. The ants in my AI ant simulation project last semester used A* to move around, for example, which was really cool to see.

We do currently have an adjacency graph (though not an adjacency list) that is returned by the World: the 2D array of tile data, which you can access by calling world.getMapTiles() (all controllers receive a reference to the world in their update method, and I assume that controllers will be used to call your A* implementation). It currently provides information about whether or not areas are passable, but the cost isn't yet implemented. Once the movement cost is available, you'll be able to pull it from there as well. So that can either be a starting point to generate whatever you want to use, or it could be used directly, depending on your preference.

If we had more time left, your work on this would also benefit the creation of Tank AI, which would be very cool!

On Wed, Apr 2, 2014 at 4:16 PM, dgoswami notifications@github.com wrote:

I would like to work on this. I know the A* and Dijkstra's shortest path algorithms. I will start by implementing the algorithm on a generic graph (probably an adjacency list) first, then work on transforming the current map/world data structure into a graph format that can be fed into the algorithm. The resulting path (sequence of graph nodes) can be transformed back into map coordinates that describes the Engineer's path.

Someone else is probably better suited to instantiating the Engineer when the relevant UI event has been registered (in Tank Controller?), then calling the A* algorithm to obtain a sequence of coordinates to travel to in order to get to the destination, and finally setting up the animation sequence. However, if I am done with the A* implementation before anyone else gets to this, I can try to work on this too.

Reply to this email directly or view it on GitHubhttps://github.com/BU-CS673/bubolo/issues/262#issuecomment-39378009 .

[dgoswami]

Aaron and Chris, thanks very much for your inputs. It's great that there is already an adjacency graph representation of the world. I can use that as a starting point.

[dgoswami]

A* coding is mostly complete. All my code is in two new files and does not make any modifications to other code. The code compiles without errors or warnings. Unfortunately testing it is difficult without a controller. I can possibly try to print some messages on the console to see what is happening, but since the Engineer controller is not implemented yet, I think it is better if I start to work on that. Meanwhile, I will create a pull request for the A* code itself since it compiles cleanly and does not impact any other code.

[ChristopherCanfield]

Was this pull request submitted? I don't see anything in the open or closed issues lists.

[dgoswami]

Brandon pulled it 3 days back, so I did not submit another request.

[ChristopherCanfield]

He pulled it into a development branch he's working on, since he wanted access to your A* work. His dev branch may or may not get into production depending on his progress.

If your work is ready, and you want it in the project, you should submit it.

On 4/23/2014 2:46 PM, Debbie wrote:

Brandon pulled it 3 days back, so I did not submit another request.

— Reply to this email directly or view it on GitHub https://github.com/BU-CS673/bubolo/issues/262#issuecomment-41199241.