Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (522)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (589)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Is there a search algorithm for this?  (Read 6387 times)
0 Members and 1 Guest are viewing this topic.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Posted 2011-08-07 12:23:51 »

I'm hoping a search algorithm exists for what I want to do, but I just don't know what it is...

Say I've got a tree made from a single root A. I have a bunch of 'rules' which can attach little sub-trees to certain existing nodes. Eg. rule 1 might attach to an A node and add children B and C, and rule 2 might attach to C and add E (via D).

My start state is an initial tree (eg. A at root and B, C, D as children) and a bunch of nodes that need to be in the tree (eg. W, X, Y, Z). The required nodes don't have to be leaves, just in the tree somewhere. I 'just' need to figure out the rules needed to expand the first tree into one that satisfies the conditions of the second.

I thought I could use STRIPS ( http://en.wikipedia.org/wiki/STRIPS ) but unfortunately that seems to require some kind of heuristic to drive the internal A* routine, and I don't think I can actually come up with a workable heuristic in this case. Sad So at the moment my only idea is a brute force approach, which is obviously going to be really slow.

Anyone any suggestions? Thanks.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #1 - Posted 2011-08-07 13:46:20 »

Interesting. What are the variables?

I'm wondering if the starting and destination nodes change, and if the rules change?

Btw what you describe, with adding branches to a tree, sounds like a Lindenmayer system. But that info is not that helpful to your search problem!

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #2 - Posted 2011-08-07 14:00:14 »

I'm not very familiar with L-systems, but yes, I believe there is quite a bit of similarity.

Interesting. What are the variables?
This is an attempt at a mission generator. So the nodes (A, B, C, etc.) are objectives like 'get the blue key'. The 'rules' are little sub-missions, like starting with a locked door and having to find the key to continue.

I'm wondering if the starting and destination nodes change, and if the rules change?[/quote]
They'll stay the same over the course of trying to construct the tree, but they'll be different the next time a tree needs to be generated. The rules will be static though (they'll be hand-made). The idea is to have lots of little hand-crafted rules and then combine them into interesting missions.

It's actually more complicated under the hood, but I don't want to give away too much detail right now.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2011-08-07 14:19:51 »

Cool stuff.

Why can't you use some kind of effort heuristic to guide an A* algorithm in its search to find the key within the tree?


Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #4 - Posted 2011-08-07 14:49:16 »

Cool stuff.

Why can't you use some kind of effort heuristic to guide an A* algorithm in its search to find the key within the tree?


I'm not sure what you mean by 'effort heuristic', could you elaborate?

At the moment I can't come up with a suitable heuristic for A* because I can't tell if any given rule is an improvement or not. It could be a good thing (ie. adding node D allows for rule 3 to be used to add node X), or it could be a complete dead end.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Roquen
« Reply #5 - Posted 2011-08-07 15:48:14 »

Sounds like applying pattern-transformation rules from a functional language or a computer algebra system.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #6 - Posted 2011-08-07 16:27:39 »

Sounds like applying pattern-transformation rules from a functional language or a computer algebra system.
Maybe? That's awfully vague - have you got any links to elaborate on that? I'm not seeing how that helps solve the problem.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline krasse
« Reply #7 - Posted 2011-08-07 19:42:47 »

This sounds very similar to parsing Context Free Grammars (CFG). There are good algorithms for this that you can use. I remember that I read something about a good bottom-up, dynamic programming approach.

Offline krasse
« Reply #8 - Posted 2011-08-07 20:33:02 »

The dynamic programming algorithm that I mentioned in the previous post is called "chart parse" and I found it in the book "Artificial Intelligence - a modern approach" second edition.

Python Implementation

Lisp implementation

For the non-child symbols, just invent a rule that can take the childrens' place.


Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #9 - Posted 2011-08-07 21:05:31 »

This sounds very similar to parsing Context Free Grammars (CFG). There are good algorithms for this that you can use. I remember that I read something about a good bottom-up, dynamic programming approach.
Yes, I had BNF in mind while I was thinking some of this up (hence the 'rules'). However I don't think 'chart parse' is applicable here - that takes a string/sequence and parses it into the component rules. I want to start with the rules and generate a sequence that matches some additional criteria.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline krasse
« Reply #10 - Posted 2011-08-07 21:15:32 »

I see, then the "algorithm" is called Hierarchical Task Network (HTN) planning. There you can expand rules and have extra preconditions. It is like Strips but more expressive.
Strips can only generate plans that can be described with regular languages while HTN-planners can generate CFG languages.

Offline krasse
« Reply #11 - Posted 2011-08-07 21:20:10 »

Here is an HTN planner implemented in Java:

Simple hierarchical ordered planner

It is an academic planner which might make it useless for anything but toy problems though Smiley

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #12 - Posted 2011-08-08 07:36:53 »

That sounds closer to what I want, but I suspect I can't break my tasks down hierarchically (which is deliberate, otherwise the results I'd get would be very predictable). Maybe I can crowbar my tasks into some sort of hierarcy just for planning though.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline krasse
« Reply #13 - Posted 2011-08-08 08:09:08 »

That sounds closer to what I want, but I suspect I can't break my tasks down hierarchically (which is deliberate, otherwise the results I'd get would be very predictable). Maybe I can crowbar my tasks into some sort of hierarcy just for planning though.

If you don't need the hierarchy, then you can use a Strips planner instead. There are many fast ones out there that I have tried myself. Try FF (fast forward), GraphPlan or some of the constraint-based such as SatPlan. You might want to look even further if you need to optimize.

Offline krasse
« Reply #14 - Posted 2011-08-08 08:10:38 »

I also found an open source implementation of FF in Java

Offline Roquen
« Reply #15 - Posted 2011-08-08 09:13:25 »

Sounds like applying pattern-transformation rules from a functional language or a computer algebra system.
Maybe? That's awfully vague - have you got any links to elaborate on that? I'm not seeing how that helps solve the problem.

Parsing grammars is an example a pattern-transformation rule system.  I was thinking more along the lines of the systems one finds past that in CAS and functional systems which search for patterns in a tree like structures and then apply the matching rule.  Note I've never played with the guts of any of these so I'm next to useless.  Also I'm not quite sure that I understand your problem statement.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #16 - Posted 2011-08-08 10:29:59 »

That sounds closer to what I want, but I suspect I can't break my tasks down hierarchically (which is deliberate, otherwise the results I'd get would be very predictable). Maybe I can crowbar my tasks into some sort of hierarcy just for planning though.

If you don't need the hierarchy, then you can use a Strips planner instead.

Which brings us full circle to my original post - I can't use a Strips planner because I don't have a suitable heuristic. Partly because I don't know which intermediate states are better or worse than others, and partly because I'm not actually after a 'shortest' path, just a valid one.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline krasse
« Reply #17 - Posted 2011-08-08 11:06:17 »


Which brings us full circle to my original post - I can't use a Strips planner because I don't have a suitable heuristic. Partly because I don't know which intermediate states are better or worse than others, and partly because I'm not actually after a 'shortest' path, just a valid one.

There are two types of Strips planners: Optimal and non-optimal. All the planners that I mentioned in the previous post are non-optimal and you don't have to provide a heuristic function, the planners use their own. Planners that are optimal use much weaker built-in heuristics because they have to be admissible.

So, if you don't care about the optimal plan, you can for example use FF, which is very fast and has a good built-in heuristic. The other planners are also very good and they all use the same language, PPDL, so you can test them all with the same problem.

Offline Jono
« Reply #18 - Posted 2011-08-08 21:28:04 »

The Java implementation of FF posted there is actually very slow - I think it was just made for educational purposes. FF isn't optimal but usually gives pretty reasonable results and optimality shouldn't matter for game levels since a few extra tasks won't hurt. Graphplan is optimal but if the problem is unsolvable there is no guarantee it will terminate.

The most popular heuristics for forward-searching planners are based on a relaxed planning graph. Basically you solve the whole problem using actions with the delete effects removed, and use the length of that solution as the heuristic distance for the actual problem. It works remarkably well. That's what FF is using but with some greedy hill-climbing. HSP also uses it but isn't optimal when actions have more than a single useful effect.

STRIPS is pretty much just a subset of PDDL and they're both just used to describe a problem. There are tons of planners out there that can solve them once you've got it in that representation. Check out the annual planning contest that's part of ICAPS.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xFryIx (62 views)
2014-11-13 12:34:49

digdugdiggy (41 views)
2014-11-12 21:11:50

digdugdiggy (34 views)
2014-11-12 21:10:15

digdugdiggy (30 views)
2014-11-12 21:09:33

kovacsa (52 views)
2014-11-07 19:57:14

TehJavaDev (56 views)
2014-11-03 22:04:50

BurntPizza (55 views)
2014-11-03 18:54:52

moogie (70 views)
2014-11-03 06:22:04

CopyableCougar4 (70 views)
2014-11-01 23:36:41

DarkCart (156 views)
2014-11-01 14:51:03
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!