Artificial Intelligence - Pathfinding, Learning and Statistics - Developers

[B]Artificial Intelligence[/B] [quote=Wikipedia]Artificial intelligence (AI) is the intelligence of machines and robots and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success. John McCarthy, who coined the term in 1956, defines it as "the science and engineering of making intelligent machines."[/quote] [URL="http://en.wikipedia.org/wiki/Artificial_intelligence"]Full Wikipedia Article[/URL] Artificial Intelligence is the form of programing to give an object a feeling of intelligence by learning from past behaviors or pre programmed behaviors; however this shell is often overshadowed by their simplistic nature at this time. Pathfinding: [quote=Wikipedia]Pathfinding or pathing refers to the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.[/quote] Pathfinding is one of the most common AI in games at the current time, with a multitude of algorithms for a range of different problems this can be very crucial and helpful AI to have in any 2D or 3D application. There are two main algorithms: [URL="https://en.wikipedia.org/wiki/A*_search_algorithm"]a*[/URL] and [URL="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm"]Dijkstra's Algorithm[/URL] both having their cons and pros. NPCs: [QUOTE=Wikipedia]A non-player character (NPC), sometimes known as a non-person character or non-playable character, in a game is any character not controlled by a player. In electronic games, this usually means a character controlled by the computer through artificial intelligence. In traditional tabletop role-playing games the term applies to characters controlled by the gamemaster or referee, rather than another player.[/QUOTE] [URL="http://en.wikipedia.org/wiki/Non-player_character"]Full Wikipedia Article[/URL] NPCs are seen in many programs from Dungeons and Dragons all the way to S.T.A.L.K.E.R. and define how the player has to handle situations. NPCs are often pre-scripted; however in some games like Black'n'White the NPCs have a learning based AI. Sorry about the short OP. I'm currently working on a A* algorithm for my game [IMG]http://i.imgur.com/IF4so.png[/IMG] What's everyone else up to relating to AI?

[QUOTE=Hiruty;39270853]What's everyone else up to relating to AI?[/QUOTE] Getting my brain fucked sideways by it.

Ah working with AI brings back such memories. Back last year or so I had a school exam about "programming games" where I chose AI as my area. I posted about it in the WAYWO thread, so you might have seen it before: [img]https://dl.dropbox.com/u/99717/StillWorking.png[/img] AI goodness that made it in the end: -Path finding with a graph (The black squares and lines) -Line of Sight -Field of View -Tracking enemies if they lost sight of them -Length of View (Could only see things as far away as the player could) -Hear sounds if they are close enough to the source -Communicate to friends while passing by if they know where the enemy is At the end of the exam I got the top grade. Quite happy with it.

[QUOTE=Zyx;39271253]Ah working with AI brings back such memories. Back last year or so I had a school exam about "programming games" where I chose AI as my area. I posted about it in the WAYWO thread, so you might have seen it before: -snip- AI goodness that made it in the end: -Path finding with a graph (The black squares and lines) -Line of Sight -Field of View -Tracking enemies if they lost sight of them -Length of View (Could only see things as far away as the player could) -Hear sounds if they are close enough to the source -Communicate to friends while passing by if they know where the enemy is At the end of the exam I got the top grade. Quite happy with it.[/QUOTE] Seeing as you probably know more than me about a*, what's some good ways of optimizing it? Using a 2D array for the grid and a tables for the openList and closedList.

A* is probably the fastest pathfinding algorithm, but it consumes quite a lot of memory compared to other algorithms. And it quite depends on what you want to optimize. If you want your algorithm to be faster, I think there isn't much you can do, apart from 'cleaning' your code (e.g. the way you find the node with the minimum F score, determining, if the current node was already opened or closed, ...). If you want to lower the memory consumption, you may even look for an alternative algorithm, such as [URL="http://en.wikipedia.org/wiki/IDA*"]IDA*[/URL].

[QUOTE=tjaze;39276441]A* is probably the fastest pathfinding algorithm, but it consumes quite a lot of memory compared to other algorithms. And it quite depends on what you want to optimize. If you want your algorithm to be faster, I think there isn't much you can do, apart from 'cleaning' your code (e.g. the way you find the node with the minimum F score, determining, if the current node was already opened or closed, ...). If you want to lower the memory consumption, you may even look for an alternative algorithm, such as [URL="http://en.wikipedia.org/wiki/IDA*"]IDA*[/URL].[/QUOTE] Yeah, went through and optimized my code and it turned out it was the way I was drawing the cells and not checking them got an extra 15FPS when running a stress test. Also I'm going to make several nodes that have paths pre calculated that NPCs search for then they make a path to that and use then use pre calculated paths to reduce strain on the searches.