Jump to content
  • Advertisement

DotStarMoney

Member
  • Content Count

    10
  • Joined

  • Last visited

Community Reputation

363 Neutral

About DotStarMoney

  • Rank
    Member

Personal Information

  1. DotStarMoney

    How will you disguise Mr. Spy?

    Hey guys! This is Chris Brown, creator of the game Nomera. In short, the project is about a spy tasked with investigating Russian numbers stations at the end of the cold war.   We've been looking for ways to reach out and get people involved with the project, so we thought we might get some input on a very special game mechanic. See, we plan for our hero, Mr. Spy: to use a wide variety of disguises... in an effort to stay unseen throughout the many places he'll have to travel! Groucho glasses won't do much, but they'll provide a constant bonus to his ability to stay unnoticed. Good luck staying hidden when dressed as a clown, but along with the shock factor, you'll find the light material and surprisingly springy shoes a boon to your running speed and jump height! Why hide behind a tree when you can be a tree! While you'll be nearly invisible in wooded environments and the outdoors, the foliage will prove a bit heavy to get around in and you'll need a few seconds to pull yourself inside of the costume. This is where you come in!   We want to know what YOU think Mr. Spy should use as a disguise, in a picture! Want to try sketching out a good spy disguise? Send it our way! Really liked your last years Halloween costume? Lets see a photo! Want to take the next step and try a pixel art disguise? We want it! (use this template to help get Mr. Spy’s ample proportions correct.) Just a picture of you in your pajamas? If you think they're good disguise pajamas, perfect! We'll be updating our page every few days with the ones we like the best as our deadline approaches. When we reach our goal, we'll incorporate your top submitted disguises into the game!   Details: The contest ends September 23, 2015 when our funding deadline is reached. Send your photos to: chris@dotstarmoney.com Please nothing NSFW! Intentionally inappropriate submissions only make it less fun :/   Thanks for reading and lets see some outfits!
  2. DotStarMoney

    Nomera, we're live!

      Hi GameDev.net!  I don't usually post here (short of this AI article I wrote here with techniques used in Nomera), but I finally have something worth sharing!   Follow the journey of Mr. Spy!  Sneak, Sabotage and Explode your way to the Truth.   Traverse Cold War Russia's most formidable environments as you solve puzzles and seek This has been a huge passion project that I'd love to have the time (so money) to complete, so please support it on Kickstarter! https://www.kickstarter.com/projects/2144358465/nomera
  3. Preamble If you're writing a "jump and run" style platformer game, you're probably thinking about adding some AI. This might constitute bad guys, good guys, something the player has to chase after etc... All too often, a programmer will forego intelligent AI for ease of implementation, and wind up with AI that just gives up when faced with a tricky jump, a nimble player, or some moving scenery. This article presents a technique to direct AI to any arbitrary static location on a map. The path an AI takes may utilize many well-timed jumps or moving scenery pieces, as long as it starts and ends in a stationary location (but this doesn't always have to be true). We'll cover the basic idea and get an implementation up and running. We'll cover advanced cases including moving platforms/destructible walls in a future article. This Technique is used in the game Nomera, at www.dotstarmoney.com or @DotStarMoney on Twitter. Before going any further, make sure you cannot implement a simpler algorithm due to constrained level geometry. I.e: all collision for levels is done on a grid of squares (most 2D games). In these cases you can get solid AI pathing with simpler techniques, this method is primarily for those who want their game AI to be human-like. Getting Ready Before we begin, it's good to have a working knowledge of mathematical graphs and graph traversal algorithms. You'll also need to be comfortable with vector maths for pre-processing and finding distances along surfaces. This technique applies to levels that are composed primarily of static level pieces with some moving scenery, and not levels that are constantly morphing on the fly. It's important to have access to the static level collision data as line segments; this simplifies things though this technique could easily be extended to support any geometric objects you use for collision. The Big Idea In layman's terms: As a developer, you jump around in the level between platforms, and the engine records the inputs you use from the point you jump/fall off of a platform, until the time you stand on the next one. It counts this as an "edge," saving the recorded inputs. When an AI wants to path through the level, he treats the series of platforms (we'll call them nodes from here on out) as vertices, and the recorded edges between them as a graph. The AI then takes a path by alternating walking along nodes, and taking the recorded input along edges to reach a destination. There are many important distinctions we'll need to make, but for now, just focus on the broad concepts. The technique we'll use is a combination of two algorithms. These are, creating the pathing graph, or "creating the data structure AI will utilize to path through the level" and traversing the pathing graph, or "guiding the enemy through the level given a destination". Obviously the latter requires the former. Creating the pathing graph is summarized as follows as follows: Load the level static collision data and compute from it a series of nodes. Load any recorded edges (paths) for the level and add these to their respective start nodes. Using the enemy collision model and movement parameters, record paths between nodes and add these to the graph. When exiting the level, export the recorded edges for the level. This might not totally make sense right now, but we'll break it down step by step. For now it's good to get the gist of the steps. Now a summary of traversing the pathing graph: Recieve a destination in the form of a destination node, and distance along that node; Calculate similar parameters for the source (starting) node. Compute a path, using any graph traversal algorithm from source to destination where the path is a series of nodes and edges. Guide the AI across a node to an edge by walking (or running, whatever the AI knows how to do) to reach the correct starting speed of the next edge in the path. Once the AI has reached the start location of the next edge in the path to some tolerance in both position and velocity, relinquish automatic control of the AI and begin control through the edges frame by frame recorded input. When recorded input ends, give control back to the automatic movement for whichever node upon which the AI stands. Repeat the last three steps until the destination has been reached Kinda getting the feel of it? Lets break down each step in detail. Implementing Pathfinding Step by Step Creating the Pathing Graph The pathing graph is made up of platforms/nodes, and connecting nodes to nodes are recordings/edges. It is important to first write hard definitions for what constitutes a platform, and what constitutes a recording. A node/platform has the following properties: It is a subset of the line segments forming the level geometry. Assuming normal gravity, all segments in the node are oriented such that their first vertex has a strictly smaller x coordinate than their second. (this would be reversed for inverted gravity) Each subsequent segment in the node starts where the last segment ended. Each segment in the node is traversable by an AI walking along its surface What does this add up to? The following key idea: A node can be traversed in its entirety by an AI walking along its surface without jumping or falling and an AI can walk to any point along the node from any other point. Here is a picture of a level's collision geometry: And here it is after we have extracted all of the nodes from it (numbered and seperately colored for clarity). In my implementation, node extraction is performed when the level is loaded, this way when a level is built you don't have to go back and mark any surfaces. You'll notice it's basically an extraction of "all the surfaces we could walk on:" NOTE: this image has a small error: 26 and 1 are two different nodes, but as you can see, they should be the same one. Depending on how your level geometry is stored, this step can take a little extra massaging to transform the arbitrary line segments into connected nodes. Another important aside, if you have static geometry that would impede the travel along a node (like a wall that doesn't quite touch down to the ground), you'll need to split nodes along this barrier. I don't have any in my example, but this will cause major complications down the road if you don't check for it. Once you have the nodes, you've completed the first step in creating the pathing graph. We also need to establish how we quantify position. A position, as used in determining sources and destinations for pathfinding, is a node (by number in this case), and a horizontal displacement along that node from its leftmost point. Why a horizontal displacement instead of an arc length along the node? Well let's say an AI collision body is a square or circle walking along a flat surface approaching an upward slope. Could its surface ever touch the interior corner point of the slope? Nope, so instead, position is measured as a horizontal displacement so we can view nodes as a "bent, horizontal line". To complete the second and third step, we need to clarify what an edge/recording is. An edge has the following properties: An edge has a start position, and destination position on two different nodes (though it could be the same node if you want to create on-platform jump shortcuts!) An edge has a series of recorded frame inputs that, provided to an AI in the edge starting position and starting velocity, will guide the AI to the position specified by the destination position A couple of things here: it is extremely neccessary that whatever generated the recorded frame input series had the EXACT collision and movement properties as the AI whose edge pathing was being created. The big question here, is where do the recorded frame inputs come from... you! Heres the jump: In Nomera's game engine in developer mode, recording can be turned on such that that as soon as the player takes a jump from a node, or falls off of a node, a new edge is created with starting position equal to the position that was fallen off of/jumped from. At this point, the player's inputs are recorded every frame. When the player lands on a node from the freefall/jump, and is there for a few frames, the recording is ended and added as an edge between the starting node and the current node (with positions of course). In other words, you're creating snippets of recorded player inputs that, if an AI is lined up with the starting position, the AI can relinquish control to these inputs to reach the destination position. Also important, when recording, the player's collision and movement properties should be momentarily switched to the AI's, and the edge marked as "only able to be taken" by the AI whose properties it was recorded with. The second step in creating the pathing graph is just loading any edges you had previously made, where the third is the actual recording process. How you do the recording is entirely up to you. Here is a screenshot of Nomera with the edges drawn on the screen. The lines only connect the starting and ending positions and don't trace the path, but it gets across the technique: In the upper left you can see marks from the in-game edge editor. This allows deletion of any edges you aren't particularly proud of, or don't want the AI to try and take. It also displays the number of frames the input was recorded for. Of course, an edge needs more properties than just the recorded frames, and starting and ending positions. As has been previously mentioned, the velocity at the start of the edge is critical as will become more obvious later. It is also beneficial to have easy access to the number of frames the edge takes, as this is useful in finding the shortest path to a destination. At this point, you should have the knowledge to build a pathing graph of platform nodes, and the recorded edges connecting them. What's more interesting though, is how AI navigates using this graph. Traversing the Pathing Graph Before we dive into how we use the pathing graph, a word on implementation. Since we're essentially recording AI actions across paths, it's a good idea to have your AIs controlled with a similar interface as the player. Let's say you have a player class that looks something like this: class Player{ public: // ... void setInputs(int left, int right, int jump); // ... private: // ... } Where "left, right, and jump" are from the keyboard. First of all, these would be the values you record per frame during edge recording. Second of all, since the AI will also need a "setInputs" control interface, why not write a REAL interface? Then it becomes reasonably more modular: enum PC_ControlMode{ MANUAL, RECORDED } class PlatformController{ public: // ... void setManualInput(int left, int right, int jump); void bindRecordedInput(RecordedFrames newRecord); int getLeft(); int getRight(); int getJump(); void step(timestep as double); // ... protected: PC_ControlMode controlMode; RecordedFrames curRecord; void setInputs(int left, int right, int jump); // ... } class Player : public PlatformController{ // ... } class AI : public PlatformController{ // ... } Now, both AI and player classes are controlled using an interface that's extendable to switch either between manual control or recorded. This setup is also convenient for pre-recorded cut scenes where the player loses control. Okay, so we want black box style methods in our AI controller like: createPath(positionType destination); step(double timestep); Where the former sets up a path between the current position and the destination position, and the latter feeds inputs to setInputs() to take the AI to the destination. In our step by step outline, createPath forms the first two steps and step, the last three. So let's look at creating the path. A path will consist of an ordered sequence, starting with an edge, of alternating nodes and edges, ending in the final edge taking us to the destination node. We first need to be able to identify our current position, be it in the air or when resting on a node. When we're on a node, we'll need a reference to that node and horizontal position along it (our generic position remember?) To build the path, we use a graph traversal algorithm. In my implementation, I used Djikstra's algorithm. For each node we store, we'll also store with it the position we'd wind up in given the edge we took to get there (we'll call this edgeStartNodeCurrentPositionX for posterity's sake). Therefore, edge weights are computed for a given edge like so: edgeFrameLength = number of frames in the edge recording walkToEdgeDist = abs(edgeStartX - edgeStartNodeCurrentPositionX) edgeWeight = edgeFrameLength * TIMESTEP + walkToEdgeDist / (HORIZONTAL_WALKING_SPEED) if(edgeDestinationNode == destinationPositionNode){ edgeWeight += abs(edgeEndX - destinationPositionX) / (HORIZONTAL_WALKING_SPEED) } As you can see, our final edge weight is in terms of seconds and is the combination of the time taken in the recording, and the time taken to walk to the start of the edge. This calculation isn't exact, and would be different if sprinting was part of enemy movement. We also check to see if we end on the destination node, and if so, the walking time from the edge end position to the destination position is added to the weight. If we can calculate our edge weights, we can run Djikstra's! (or any other graph traversal algorithm, A* is fine here if you use a "euclidian distance to the destination" type heuristic). At this point, you should have a path! We're almost there, and to cover the 4 steps of the outline, there's not a lot to do. Basically, we have two procedures that we switch between depending on whether or not we stand on a node, or are being controlled by an edge recording. If we're on a node, we walk from our current position in the direction of the edge we have to take next. Now I mentioned previously that we also need to know the starting velocity of recorded edges. This is because, more often than not, your AI might have a little acceleration or decceleration when starting or stopping from walking. One of these transitional speeds may have been the point when the target edge began. Because of this, when we're walking towards the edge start location, we might have to slow down or back up a bit to take a running/walking start. Once we reach the start position of the edge we're going to take, more than likely, our position will not match the edge start position exactly. In my implementation the position was off rarely more than half of a pixel. What's important is that we reach the edge start position within some tolerance, and once we do, we'll snap the position/velocity of the AI to those of the edge start position/velocity. Now we're ready to relinquish control to the edge recording. If we're on an edge, well, each frame just adopts the controls provided by the edge recording and increase the number of the recorded frame that we read. Thats it! Eventually, the recording will finish, and if the recording was frame perfect, the AI will land on the next node and the node controls will take over. Some Odds and Ends There are a few things you can do to tune this technique for your game. It's highly recommended that you add an in-game path recording and deleting interface to help you easily build level pathing: Nomera takes about 10m to set up level pathing and its pretty fun too. It's also convenient to have nodes extracted automatically. While you technically could do it yourself, adding automatic extraction makes the workflow VASTLY easier. For fast retrieval of node parameters, Nomera stores all of the nodes in a hash table and all of the edges in lists per node. For easy display, edges are also stored in a master list to show their source/destination lines on the screen. If you didn't notice already, static interactive pieces like ladders or ropes that aren't collidable objects are automatically handled by this technique. Let's say you need to press "up" to climb a ladder, if that "up" press is recorded and your AI uses a similar interface to the one previously proposed, it will register the input and get to climbing. Wrap Up We've looked at a way to guide AI around a platforming level that works regardless of collision geometry and allows AI to take the full potential of their platformer controls. First, we generate a pathing graph for a level, then we build a path from the graph, and finally we guide an AI across that path. So does it work? Sure it does! Heres a gif: These guys were set to "hug mode." They're trying to climb into my skin wherever I go. If you have any questions or suggestions, please shoot me an email at chris@dotstarmoney.com. Thanks for reading! Update Log 27 Nov 2014: Initial Draft 4 Dec 2014: Removed a line unrelated to article content.
  4. DotStarMoney

    Generalized Platformer AI Pathfinding

    I might disagree with you in that FreeBASIC feels very C like when you're working with it due to the manual memory management and missing fluff a lot of modern languages have. I do agree with you though that the line probably isn't very helpful.
  5. DotStarMoney

    Generalized Platformer AI Pathfinding

      A good question! Since any point on a node, by design, is uniquely identifiable on that node by its x coordinate (does this line make sense?), I sweep through all nodes minimum and maximum bounding x coordinate and find those which the AI's centroid is between. Then in that set, I find the corresponding y coordinate that lines up with the AI's centroid.x on each node (again, pretty easy since nodes by construction are just a bunch of left-to-right line segments). The node the AI is standing on is the one whose calculated y coordinate is closest to the feet of the player.   This is done every frame the physics system determines the AI is grounded. In my implementation there are some slop frames for the player's "grounding state" so that little hops due to angled geometry don't throw the engine into recording mode and take up space.   Should I include this in the article? Or is this too implementation specific?
  6. DotStarMoney

    Generalized Platformer AI Pathfinding

      I included that line because I wanted to put the code required in perspective considering not many people are familiar with the language (I ended up using it for Nomera because Nomera started as a competition piece where the language asked WAS FreeBASIC).   As a reader, what do you think would have been a preferred way to say the same thing? Maybe I shouldn't mention the language at all?
  7. DotStarMoney

    Best comment ever

    Well right, it just doesn't FEEL like it should!
  8. DotStarMoney

    How would I go about developing a console like ps1 or n64

    You know who I learned a surprisingly large amount of retro-hardware construction from? Ben Heck.   Check out his youtube: https://www.youtube.com/channel/UChturLXwYxwTOf_5krs0qvA   He builds a lot of retro computers (and game consoles!!) and explains what hes doing in surprising detail. I'm at the point in my computer engineering career where I feel I could build a console, and this guy really knows what hes talking about.
  9. DotStarMoney

    Best comment ever

    These are hilarious. During my undergrad I was working on a partner project and found this in a 20 line .c file: ;;;;; ;;;;;; ;; ;; ;; ;;;;;;; ;;;;;;; ;; ;;;;;;; ;; ;; ;;;;; ;; ;; ;;;; ;;;; ;; ;; ;; ;; ;; ;; ;;; ;; ;; ;;;;; ;;;;;; ;; ;; ;; ;; ;;;;;; ;; ;; ;; ;; ;; ;; ;; ; ;; ;;;;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;;; ;; ;;;;; ;;;;;; ;; ;; ;; ;;;;;;; ;;;;;;; ;;;;;;; ;;;;;;; ;; ;; ;;;;; Which much to my surprise compiles just fine.
  10. DotStarMoney

    An easy approach to platformer pathfinding

    Oh that looks like a good idea! I think I will, thanks!
  11. DotStarMoney

    An easy approach to platformer pathfinding

    Thanks, I'm tryin'!   Yeah, the idea here was to avoid set "waypoints," or work in such a way that AI navigation wasn't limited to places you had been before. Player recordings are only taken between platforms the engine deems "too tricky to automatically path to"   In this case actually merging nodes would defeat the purpose of them, as their "traversable in their entirety by just mosying left and right" property keeps the code for the algorithm pretty simple and gives the illusion of completely autonomous movement; graph refinement might actually make the pathing worse! If by A* you mean I should include a heuristic to the pathfinding algorithm, then I do. It explores paths "in the direction" of the target first, which in affect behaves like a priority queue would. Really the search runs so comically fast given the pitance of nodes (medium sized maps tend to have around 40) that I can't imagine A* would offer much in the way of an improvement.
  12. I'm working on a platformer game right now where I wanted enemies to really feel like the computer was trying to kill you. Not like, "oh, you went too far away or you climbed on that moving thing I don't know how to use, later..." I had some complicated ideas about fitting a curve to a weighted space, but didn't want to spend a large chunk of development time on research. The method I implemented to get the human-like AI I needed is as follows (also, I should mention, if you're interested, the game is called Nomera: we have a website www.dotstarmoney.com and a twitter @DotStarMoney):   As a preamble, the game uses a custom physics engine and all surfaces are represented by circles or line segments. Moving platforms can either rotate at a speed following a periodic function, follow a periodic path, or be toggle-able via switch.   1) The engine splits the level up into "nodes," or, a surface that an AI could visit in its entirety just by walking. These constitute flat static surfaces that could have slopes but no breaks or (all of) moving platforms, this is done when a map is loaded.   2) If in recording mode (press a key, 'M' in this case), the game tracks the node that you stand on. AS SOON AS you jump, or fall off of a static surface, the engine starts recording your keypresses. In recording mode, the players object properties are set to those of the enemy paths you wish to record (so in my case, I want to record soldier movement, so the engine sets my mass, collision shape, friction, etc... to that of the soldier). AS SOON AS you land on a STATIC surface, the recording is finished and the engine stores the path between the two static surfaces and the recorded per-frame key presses.   For moving objects, the game also records the cyclic_time of the object, that is, the point in its periodic movement (or start point/end point if a toggle) of the moving platform. The path will only be recorded if the moving platforms traversed have periods that are a small (< 4) integer multiple of each other.   As a developer, its my job to jump around for a bit, record some good paths, delete some if they're bad (these realtime functionality to do this), and make sure the enemy has options.   A screenshot of some recorded paths(edges).   3) With a whole bunch of stored pathing (this works as you record too!), if an enemy needs to get from point A, to B, where B can be you/close enough to you to shoot/something to investigate/a switch for a moving platform, he runs Djikstra's algorithm on the node graph, keeping track of where he ends up on the node after each edge to ensure he takes the fastest of the possible edges where two nodes have multiple connecting edges. For the easier enemies, they're barred from taking paths where sprinting is involved or random weights are distributed during the graph routing.   4) With the path in hand, an enemy will alternate, walking/running along a node to reach the start of the edge he must take, if he needs a running start, he'll instead try to get to a point where he can build up the correct speed. Once an edge is reached at the proper position/velocity (within a teeny tolerance, about half of one pixel for position and half of pixel/second for veloctiy), the enemy snaps his position/velocity to the edges start position/velocity and as I like to call it, runs "Jesus take the wheel." The recorded inputs take over and move the enemy to the next node to repeat the process.   In the case where an enemy must take a moving platform, he'll stand at the node waiting for the cyclic_time of the platform to line up to the recording (this is why multiple platforms must have periods that are multiples of one another) before he takes the edge, handing control over to the recorded edge movement.   5) Thats it! This logic is packed into a few routines and they're used by the enemy logic for the fun programming (actual behavior). Heres a gif of some pathing in action:   These dipsticks were set to "hug" mode, where they must reach the target and get real close at all costs.   I can make a more interesting vid if desired, this is just what I created from a level I'm working with right now. Thanks for reading!
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!