Artificial Intelligence Tools Extension (Beta Release 8)

Artificial Intelligence Tools Extension

"Artificial Intelligence Tools Extension" provides some additional blocks for working with graphs. It is a general-purpose graphs toolset, which includes an implementation of A* pathfinding.

The purpose of the "Artificial Intelligence Tools Extension" is to solve graph-related decision-making problems. Some example applications include:

• Solving a maze
• Finding the best path from point A to point B
• Identifying if two areas are connected
• NPC in a real-time strategy game needs to research upgrades to produce a desired product. In what order are the upgrades researched?

Download

The extension can be downloaded here (.zip),  here (.tar.gz), or from my site (.zip or .tar.gz).

A sample project file can be downloaded here or from my site.

Old Releases are available from my Archives Page

Please see: How to Install and Update an Extension.

General Features

Basic features of this extension include:

• Customize costs of edges
• Name nodes and connections
• Not strictly map-based. For maze-solving and path-finding, paths can include "teleports" (doors, etc.)
• Multiple graph management
• Quick implementation (solve a basic path-finding problem with only two blocks)
• Customizable heuristic function
• Ability to export the entire graph to a list (useful for debugging)

Quick Reference

All documentation can be found at my site.

Version History

2015-11-24:  (Beta Release 1) Initial release. Added 10 blocks.

Beta release notes: These are the ten blocks that were required to solve my own problem. I can add more blocks if requested.

Please note that this is a beta release. There may be a few bugs that slipped through the cracks. Please let me know if you find any 

2015-11-30:  (Beta Release 2) Added graph drawing block.

2015-12-02:  (Beta Release 3) Bug fix.

Technical Details: There is a bug in the A* implementation that can cause AStar.pathToArray to hang. A* stores information about nodes it has visited in the node itself. Added a function that resets this data each time AStar.findPath is called, so that data from previous searches does not contaminate future searches.

2016-07-20:  (Beta Release 4) Added 12 new blocks.

2016-09-29:  (Beta Release 5) Fixed bug in blocks.xml.

2016-10-15:  (Beta Release 6) Addressed issue with 'cost of path' block in Flash builds. See bottom of page 2 of this thread for details.

2016-11-06:  (Beta Release 7) Bug fixes.

2018-04-08:  (Beta Release 8) Stencyl 3.5 layer compatibility fixes for autograph function. Credit: yoplalala

I'm trying to apply it to an enemy to test pathfinding.

No matther what I try, it just finds the direct route, ignoring walls like nothing

I'm trying to apply it to an enemy to test pathfinding.

No matther what I try, it just finds the direct route, ignoring walls like nothing

How are you generating the graph?

If you're using the "generate graph" block, it looks for tiles with collision shapes defined. It uses the same function as the similar block in the Tile API (using -1 for layer ID). A simple test that it's working right would be to use the block in the Tile API to see if there is a collision shape at one of the walls that is being ignored. If there's no shape, the auto-graph won't work.

Definitely a tile there

I've tried generating a graph using scene events, as well as on the movement behaviour itself, to no avail

Can you attach a screenshot of the code you're using to implement the graphs?

Getting "The engine extension 'raycastapi' does not exist" error with v3.3.2 and the latest extension and the sample project. The project runs fine, but on loading I get the above error. Any ideas?

Scene Event

Attached to actor

Ignore the created and periodic events, they're just old attempts/deactivated

Getting "The engine extension 'raycastapi' does not exist" error with v3.3.2 and the latest extension and the sample project. The project runs fine, but on loading I get the above error. Any ideas?

I just ran into that myself while testing on another computer. I must have left the raycasting API enabled when I exported that demo. You can ignore that error--I don't use any of those blocks. When I'm able to, I'll re-export the project so that warning doesn't show up.

@UnrealCanine:

I can't seem to reproduce the error. The culprit has to lie within the generate graph block. The find path block can only look for a path on tiles that correspond to nodes on the graph. So, for whatever reason, your walls are being included on the graph.

The generate graph block uses collision shapes. If the tiles have no collision shapes defined in the tileset editor, then the generate graph block will be "blind" to them.

What does debug draw show? If debug draw shows no collision boxes around the tiles, then the auto generation won't work either.

One thing I noticed is that you're using item 0 for xlist and item 1 for ylist. The extension uses row and column, not x and y.

Try using item 0 for ylist and item 1 for xlist. Also, in your use of the "best path" block, you're using x for row instead of column. Row should be floor of Y of self / 16, not X of self.

Ayy, got it working to some degree. Thanks

Ayy, got it working to some degree. Thanks

The graph was rotated by 90 degrees and. It looks like, just by coincidence, the correct corridor (to the left) happened to lead straight to the target if it was rotated.

When I get a chance, I might be able to condense all the code required to draw the graph over the screen into a single block. That would catch these types of problems.

Two quick updates--

- Added a drawing block which will draw the graph over the screen. This should make debugging graph generation a lot easier. Example usage:



- Re-exported the demo file with the raycast API removed. This should take care of the error mentioned in the previous posts.

Beta Release 3 released--this update fixes a bug that can cause a hang/crash if A* is called multiple times on the same graph. Beta Release 1 and 2 are affected by this bug, so should not be used.

Thank you for this. I've read through several explanations, watched a few videos. Tried to adapt some example pseudo code to stencyl for A*, but no matter what I did I just couldn't wrap my brain around it. Then I found your extension. Thanks to you, it's all working now.
You're awesome.