<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Re: Stack-Based NPC AI --> <!--X-From-R13: [nex Uevggre <znexNreqbf.Egnasbeq.SRG> --> <!--X-Date: Sun, 6 Dec 1998 16:06:59 -0800 --> <!--X-Message-Id: 199812070006.QAA01598#erdos,Stanford.EDU --> <!--X-Content-Type: text --> <!--X-Reference: 001501be2169$112e9220$1896ce80@greymud --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] Re: Stack-Based NPC AI</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:mark#erdos,Stanford.EDU"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00910.html">Previous</a> | <a href="msg00912.html">Next</a> ] Thread: [ <a href="msg00930.html">Previous</a> | <a href="msg00914.html">Next</a> ] Index: [ <A HREF="author.html#00911">Author</A> | <A HREF="#00911">Date</A> | <A HREF="thread.html#00911">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] Re: Stack-Based NPC AI</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] Re: Stack-Based NPC AI</LI> <LI><em>From</em>: Mark Gritter <<A HREF="mailto:mark#erdos,Stanford.EDU">mark#erdos,Stanford.EDU</A>></LI> <LI><em>Date</em>: Sun, 6 Dec 1998 16:06:47 -0800 (PST)</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> Eli Stevens writes: > > Every mob would have a "base state" that makes them act a certain way when > they have nothing else on their to-do stack. There would also be triggers > that would push a new to-do action onto the stack. When that action was > finished, it would pop itself off of the stack, allowing whatever was > beneath it on the stack to be done. > [example snipped] > > It seems to me that with some imaginative coding, and careful thought > to the triggers and actions, a very realistic-ish world could be set > up... Of course, if there are not enough triggers and actions, the > mobs might all act the same, but that's better than nothing, right? > I played around with something of the sort a while back. A couple issues I encountered were: -- Subgoals need to be retracted if the goal they're trying to accomplish gets met. (For example, if I see Boffo get killed, I no longer need to go round up my friends and take him out.) -- Intelligent actors should try to batch their goals together. If I have to pick up something to eat as well as buy components for a spell, it's much preferable to do both in one trip rather than having a stack like: go to food store buy bread go to house eat bread go to magic store buy lizard warts go to house cast spell Reordering should be allowed, too: if a goal has two subgoals (A and B), the character should be able to choose which one to pursue first and change its mind later (if, for example, a new triggered goal brings it "closer" to accomplishing B instead of A.) I feel that the natural structure is more of a tree than a stack. -- Distraction. If triggers aren't balanced correctly, the character tends to build large stacks without accomplishing many goals. Some means of ignoring or collapsing the stack would probably be good. A related AI/robotics strategy is "subsumption architecture". You might want to do some searching about that. (The examples I've seen of subsumption architectures generally don't keep state around--- it's a fixed set of goals with a fixed ordering, if I remember correctly.) You might try <URL:<A HREF="http://ai.eecs.umich.edu/cogarch0/subsump/">http://ai.eecs.umich.edu/cogarch0/subsump/</A>> The "Angband Borg" uses a goal-based (but not stack-based) approach, but you might find it interesting: <URL:<A HREF="http://www.phial.com/angborg/">http://www.phial.com/angborg/</A>> As far as I know, most of the AI research for planning deals more with how to achieve goals than to set them up, unfortunately. Still, the "AI on the Web" page for Norvig + Russel's AI book might be a good place to start from that end: <URL:<A HREF="http://www.cs.berkeley.edu/~russell/ai.html">http://www.cs.berkeley.edu/~russell/ai.html</A>> Mark Gritter mark#erdos,stanford.edu </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <ul compact><li><strong>Follow-Ups</strong>: <ul> <li><strong><A NAME="00914" HREF="msg00914.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong> <ul compact><li><em>From:</em> Par Winzell <zell#alyx,com></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <UL><LI><STRONG>References</STRONG>: <UL> <LI><STRONG><A NAME="00909" HREF="msg00909.html">[MUD-Dev] Stack-Based NPC AI</A></STRONG> <UL><LI><EM>From:</EM> "Eli Stevens (KiZurich)" <c718157#showme,missouri.edu></LI></UL></LI> </UL></LI></UL> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00910.html">[MUD-Dev] Re: Stack-Based NPC AI</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00912.html">[MUD-Dev] Re: Stack-Based NPC AI</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00930.html">[MUD-Dev] Re: Stack-Based NPC AI</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00914.html">[MUD-Dev] Re: Stack-Based NPC AI</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00911"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00911"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><STRONG>[MUD-Dev] Re: Introduction</STRONG>, <EM>(continued)</EM> <ul compact> <ul compact> <LI><strong><A NAME="00945" HREF="msg00945.html">[MUD-Dev] Re: Introduction</A></strong>, Mik Clarke <a href="mailto:mikclrk#ibm,net">mikclrk#ibm,net</a>, Wed 09 Dec 1998, 07:15 GMT </LI> </ul> </ul> </LI> <LI><strong><A NAME="00909" HREF="msg00909.html">[MUD-Dev] Stack-Based NPC AI</A></strong>, Eli Stevens (KiZurich) <a href="mailto:c718157#showme,missouri.edu">c718157#showme,missouri.edu</a>, Sun 06 Dec 1998, 22:38 GMT <UL> <LI><strong><A NAME="00910" HREF="msg00910.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, Richard Woolcock <a href="mailto:KaVir#dial,pipex.com">KaVir#dial,pipex.com</a>, Mon 07 Dec 1998, 00:00 GMT <UL> <LI><strong><A NAME="00930" HREF="msg00930.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, Mik Clarke <a href="mailto:mikclrk#ibm,net">mikclrk#ibm,net</a>, Mon 07 Dec 1998, 21:35 GMT </LI> </UL> </LI> <LI><strong><A NAME="00911" HREF="msg00911.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, Mark Gritter <a href="mailto:mark#erdos,Stanford.EDU">mark#erdos,Stanford.EDU</a>, Mon 07 Dec 1998, 00:06 GMT <UL> <LI><strong><A NAME="00914" HREF="msg00914.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, Par Winzell <a href="mailto:zell#alyx,com">zell#alyx,com</a>, Mon 07 Dec 1998, 01:18 GMT <UL> <LI><strong><A NAME="00925" HREF="msg00925.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, David Bennett <a href="mailto:ddt#discworld,imaginary.com">ddt#discworld,imaginary.com</a>, Mon 07 Dec 1998, 20:03 GMT </LI> <LI><strong><A NAME="00926" HREF="msg00926.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, David Bennett <a href="mailto:ddt#discworld,imaginary.com">ddt#discworld,imaginary.com</a>, Mon 07 Dec 1998, 20:05 GMT </LI> </UL> </LI> </UL> </LI> <LI><strong><A NAME="00912" HREF="msg00912.html">[MUD-Dev] Re: Stack-Based NPC AI</A></strong>, Marc Hernandez <a href="mailto:marc#ias,jb.com">marc#ias,jb.com</a>, Mon 07 Dec 1998, 00:22 GMT </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>