• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By GytisDev
      without going into any details I am looking for any articles or blogs or advice about city building and RTS games in general. I tried to search for these on my own, but would like to see your input also. I want to make a very simple version of a game like Banished or Kingdoms and Castles,  where I would be able to place like two types of buildings, make farms and cut trees for resources while controlling a single worker. I have some problem understanding how these games works in the back-end: how various data can be stored about the map and objects, how grids works, implementing work system (like a little cube (human) walks to a tree and cuts it) and so on. I am also pretty confident in my programming capabilities for such a game. Sorry if I make any mistakes, English is not my native language.
      Thank you in advance.
    • By Descent
      Wow what a wild game by GalaXa Games Entertainment Interactive. Play now... it's really fun but IF you have epilepsy then don't play. It does not feature flashing pictures, but there is lots of animated stuff that might get ya. Anyway, 4 levels, 2 endings, insane action, BY INFERNAL. Please play it, right nao! Also , nice midi music composed by me is in the game.
    • By Armantium
      Killing Floor 2 has the best dismemberment/gore system by far.
      No other game comes even close; how enemies react, segmented body parts depending where you shoot them, how dead bodies react, etc.
      Is there an easy-to-set up system, but with scaled down features, for the Unreal Engine 4, while still offering the same visceral physicality?
    • By GameDev.net
      This is an extract from Practical Game AI Programming from Packt. Click here to download the book for free!
      When humans play games – like chess, for example – they play differently every time. For a game developer this would be impossible to replicate. So, if writing an almost infinite number of possibilities isn’t a viable solution game developers have needed to think differently. That’s where AI comes in. But while AI might like a very new phenomenon in the wider public consciousness, it’s actually been part of the games industry for decades.
      Enemy AI in the 1970s
      Single-player games with AI enemies started to appear as early as the 1970s. Very quickly, many games were redefining the standards of what constitutes game AI. Some of those examples were released for arcade machines, such as Speed Race from Taito (a racing video game), or Qwak (a duck hunting game using a light gun), and Pursuit (an aircraft fighter) both from Atari. Other notable examples are the text-based games released for the first personal computers, such as Hunt the Wumpus and Star Trek, which also had AI enemies.
      What made those games so enjoyable was precisely that the AI enemies that didn't react like any others before them. This was because they had random elements mixed with the traditional stored patterns, creating games that felt unpredictable to play. However, that was only possible due to the incorporation of microprocessors that expanded the capabilities of a programmer at that time. Space Invaders brought the movement patterns and Galaxian improved and added more variety, making the AI even more complex. Pac-Man later on brought movement patterns to the maze genre – the AI design in Pac-Man was arguably as influential as the game itself.
      After that, Karate Champ introduced the first AI fighting character and Dragon Quest introduced the tactical system for the RPG genre. Over the years, the list of games that has used artificial intelligence to create unique game concepts has expanded. All of that has essentially come from a single question, how can we make a computer capable of beating a human in a game?
      All of the games mentioned used the same method for the AI called finite-state machine (FSM). Here, the programmer inputs all the behaviors that are necessary for the computer to challenge the player. The programmer defined exactly how the computer should behave on different occasions in order to move, avoid, attack, or perform any other behavior to challenge the player, and that method is used even in the latest big budget games.
      From simple to smart and human-like AI
      One of the greatest challenges when it comes to building intelligence into games is adapting the AI movement and behavior in relation to what the player is currently doing, or will do. This can become very complex if the programmer wants to extend the possibilities of the AI decisions.
      It's a huge task for the programmer because it's necessary to determine what the player can do and how the AI will react to each action of the player. That takes a lot of CPU power. To overcome that problem, programmers began to mix possibility maps with probabilities and perform other techniques that let the AI decide for itself how it should react according to the player's actions. These factors are important to be considered while developing an AI that elevates a games’ quality.
      Games continued to evolve and players became even more demanding. To deliver games that met player expectations, programmers had to write more states for each character, creating new in-game and more engaging enemies.
      Metal Gear Solid and the evolution of game AI
      You can start to see now how technological developments are closely connected to the development of new game genres. A great example is Metal Gear Solid; by implementing stealth elements, it moved beyond the traditional shooting genre. Of course, those elements couldn't be fully explored as Hideo Kojima probably intended because of the hardware limitations at the time. However, jumping forward from the third to the fifth generation of consoles, Konami and Hideo Kojima presented the same title, only with much greater complexity. Once the necessary computing power was there, the stage was set for Metal Gear Solid to redefine modern gaming.
      Visual and audio awareness
      One of the most important but often underrated elements in the development of Metal Gear Solid was the use of visual and audio awareness for the enemy AI. It was ultimately this feature that established the genre we know today as a stealth game. Yes, the game uses Path Finding and a FSM, features already established in the industry, but to create something new the developers took advantage of some of the most cutting-edge technological innovations. Of course the influence of these features today expands into a range of genres from sports to racing.
      After that huge step for game design, developers still faced other problems. Or, more specifically, these new possibilities brought even more problems. The AI still didn't react as a real person, and many other elements were required, to make the game feel more realistic.
      Sports games
      This is particularly true when we talk about sports games. After all, interaction with the player is not the only thing that we need to care about; most sports involve multiple players, all of whom need to be ‘realistic’ for a sports game to work well.
      With this problem in mind, developers started to improve the individual behaviors of each character, not only for the AI that was playing against the player but also for the AI that was playing alongside them. Once again, Finite State Machines made up a crucial part of Artificial Intelligence, but the decisive element that helped to cultivate greater realism in the sports genre was anticipation and awareness. The computer needed to calculate, for example, what the player was doing, where the ball was going, all while making the ‘team’ work together with some semblance of tactical alignment. By combining the new features used in the stealth games with a vast number of characters on the same screen, it was possible to develop a significant level of realism in sports games. This is a good example of how the same technologies allow for development across very different types of games.
      How AI enables a more immersive gaming experience
      A final useful example of how game realism depends on great AI is F.E.A.R., developed by Monolith Productions. What made this game so special in terms of Artificial Intelligence was the dialog between enemy characters. While this wasn’t strictly a technological improvement, it was something that helped to showcase all of the development work that was built into the characters' AI. This is crucial because if the AI doesn't say it, it didn't happen.
      Ultimately, this is about taking a further step towards enhanced realism. In the case of F.E.A.R., the dialog transforms how you would see in-game characters. When the AI detects the player for the first time, it shouts that it found the player; when the AI loses sight of the player, it expresses just that. When a group of (AI generated) characters are trying to ambush the player, they talk about it. The game, then, almost seems to be plotting against the person playing it. This is essential because it brings a whole new dimension to gaming. Ultimately, it opens up possibilities for much richer storytelling and complex gameplay, which all of us – as gamers – have come to expect today.
    • By lucky6969b

      Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
  • Advertisement
  • Advertisement

Pathfinding Is A* good when entities should collide with eachother?

Recommended Posts


A* is about finding paths, or more abstractly, about finding the cheapest route through a graph, that's all. It has no opinion on entities or collision between them.

You can recalculate a new A* path when the current one ends up being blocked, and that is often good enough. There are also things you can do with A* to try and reduce collisions, such as change the weight of nodes when you know other entities will be occupying them. You can use steering behaviours or crowd/flocking algorithms when navigating along the A* path to give entities some degree of freedom to avoid each other while following paths. You could share paths among friendly entities so that they can form an orderly line when passing along the same path instead of competing for chokepoints.

There are also more advanced algorithms that attempt to acknowledge the fact that the environment can change, and that a path that was previously found may not always continue to be the best one when other entities become involved. These algorithms are generally based on A*, so you can start with a good A* implementation and adapt it to one of these algorithms later if you need.

Share this post

Link to post
Share on other sites

With this problem I recommend using steering(obstacle avoidance) for entities every frame, it's pretty good for short-range maneuvering. Couple it with A* for longer range navigation which you can run sparingly.

Share this post

Link to post
Share on other sites

Have a look at steering as well as avoidance algorithms such as ORCA, Reciprocal Velocity Obstacles, etc. A* is for strategy, avoidance is for tactics. A* will tell you what route to take, steering and other avoidance mechanisms will give you the details of how to follow that route, including moment-to-moment accelerations for obstacle avoidance.

Share this post

Link to post
Share on other sites

That said, if you are working on a low rez game such as a turn-based game where pieces are on a grid board, there are ways you can incorporate the locations of objects into your A*. For example, there are articles that talk about not only blocking the location of pieces currently, but blocking locations where they will be on future turns. The problem is you have to keep phantom copies of the "board" for those times in the future and iterate through them as you do your pathfinding search. e.g. for step 1, I can use the current locations, for step 2, I use where people are going to be 1 step into the future, step 3, 2 steps into the future, etc. Get's kind of intractable after a bit.

Share this post

Link to post
Share on other sites

My grid agents will flag the node they are standing on/moving to as Occupied and I've implemented an option into my A* that basically says Occupied nodes are unwalkable and skips them during the search much like it would a node marked as unwalkable/wall/etc.  It makes for somewhat boxy movement much like Warcraft 3 or the original Starcraft I suppose.

Since paths are calculated on a single frame I can't determine what nodes might have changed and become occupied after an agent has already calculated a path, so if a node along the agent's path becomes occupied after the fact he will walk right through it.  To counter this, in my update loop (if the agent is currently moving) I determine what node the agent will be standing in next, and if it's occupied the agent will stop, stall for a brief moment, then calculate another path.

I recorded a quick video to show what this looks like:


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement