Archived

This topic is now archived and is closed to further replies.

Flint

Algorithms and Data Structures

Recommended Posts

Soon, after I have a strong foundation of knowlege with C++ I''m going to start learning about Algorithms and Data Structures. I''ll be reading a book by Robert Sedgewick called "Algorithms in C++, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition)". Eventually, after I''ve aquired some programming skills that will be helpful through college, and that can be applied to many fields, I might get into video game programming. I know they use algorithms in game AI and I would like to know if my book would help me any if I ever began programming my own game AI. Could some of you more experience game programmers give me a brief description on how you implement algorithms and data structures in game AI, or in video games entirly if you can. If I do ever get into programming game AI, I''ll probably get a book covering that topic explicitly. I was just wondering if my book would help me with that topic later on, and how. Thanks a lot. "You only have one life, so make it count"

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"AI" is a vague topic. It gets talked about in a general way when applied to games, but it''s too broad of a subject. AI really only makes sense in the context of a game. If you''re talking about Chess or Checkers or Go, then that''s one thing, but if you''re talking about AI for Final Fantasy or Unreal then that''s something else.

You need to phrase your question in terms of specifically what it is that you want to do. In the great majority of cases, game AI is just a bunch of simple rules, like "determine which unit is weakest and attack it."

Share this post


Link to post
Share on other sites
For that matter "algorithms" is a vague topic. Which one of the millions (and increasing) do you want to know about? I suppose we could start a project to list them all here...

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

Share this post


Link to post
Share on other sites
Could you please define what an algorithm is? What are sorting and searching algorithms? How do they work with data structures? I''m not totally clueless about this, but I''d still like to know more about it. Thanks.

"You only have one life, so make it count"

Share this post


Link to post
Share on other sites
Uhm..an algorithm is nothing more than a procedure (sequence of code) that solves a problem. There''s no magic to it..

Data structures is a very broad topic. How does a search algorithm work with data structures?

A search algorithm searches data for items that match the search query. It''s not that complicated.


swift URL | browse my bookmarks [server may not always be on]

Sensimed | Info/download

Share this post


Link to post
Share on other sites
an Algorithm is just a method for accomplishing a goal, a recipie is one example of an algorithm, you have your inputs (ingredients), your code (directions), and output (the cookies or what have you). What your inputs and outputs are and how the code is represented differes between applications. We, as programmers, tend to use psuedo-code to describe an algorithm.

A data structure is harder to explain. what it boils down to is that a data structure is something designed to hold related groups of information. For example, people have names, birthdays,hair and eye colours. these attributes could all be contained in one data structure,In psuedo code

struct person
{
name:string;
birthday:date;
hair_colour:colour;
eye_colour:color;
}

using this we can then declare variables (A: Person) that contain all the data of the data structure and allow us access to individual records (A.name).

sorting and searching algorithms are just methods for sorting a set of data or for finding a specific piece of data in a set.

[edited by - Simage on December 25, 2002 2:19:17 PM]

Share this post


Link to post
Share on other sites
"!THIS is in the AI forum? Wow."

Some AI is 100% data structures and algorithms so I don't think the OP's question is irrelevant. How do you propose, for example, to instruct someone how to calculate the shortest path between two waypoints without discussing data structures and algorithms?

In answer to your question Flint, the more you know about data structures and algorithms, the more able you will be to implement the majority of AI techniques. Sedgewick's other book (part 5, graphs) is particularly relevant.





ai-junkie.com

[edited by - fup on December 26, 2002 3:01:15 AM]

Share this post


Link to post
Share on other sites
One would be hard pressed to implement AI without the knowledge of reading and writing, and yet we don''t usually offer instruction on that in here. My point was only that there seems to be a vast gulf between Flint''s knowledge level ("Soon, after I have a strong foundation of knowlege with C++" ) and AI. I am thinking that the "for beginners" forum would be a more appropriate place to start.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

Share this post


Link to post
Share on other sites
An algorithm has a specific definition... you can find the definition in many books, particularly the Art of Computer Programming has a good one.

It takes input
It does something to it
It has an output
It must produce a result in a finite number of steps
It must be possible to replicate the results of an algorithm with pen and paper (it is finite, and conceivable, that a human being can do it)

There are types of code that are not algorithms... sometimes you call them heuristics, sometimes you call them procedures.. in any case, they do not meet the definition of what an algorithm is.

A data structure is just a means of applying an algorithm onto a structure (in computer memory). Data structures are meant to store data in a consistent way that it is possible to use an algorithm to find that data, and manipulate it. An array is a basic data structure.

Algorithms and data structures go hand in hand.

Yes, the Sedgewick books are great for a resource on the topic. The Art of Computer Programming is the de facto academic books, very hard, but very detailed. Sedgewick studied under Knuth so it''s no surprise his books are good... and for most purposes I think you are much better off with Sedgewick than Knuth unless you are interested in academic issues and code that runs on a virtual machine in assembler

Hrrm as for it''s applicability to AI... the science of AI pretty much fathered the art of algorithms and data structures. Languages like Lisp incorporated the idea of linked lists into programming concepts. We take link lists for granted now.. once it was considered an AI concept.

The best book around I know of on the basics of Ai is "AI: A modern approach" by Peter Norvig and others. It contains information about AI topics, algorithms and data structures.
It''s used in intro AI courses in college.
















Share this post


Link to post
Share on other sites