Bot navigation/LOS through rectangular tiles?

you can use the a-star algorithm for navigation. as for line of sight, it can be done in 2 ways really.

1) 4-axis viewing
if you limit the entity to only being able to see in the up, down, left and right directions ONLY, then first of all you check to see if the enemy is either on the same row or column as you on the map (if (ent1.x == ent2.x || ent1.y == ent2.y)). If so, just loop through all tiles in the direction of the enemy. if one of them is anything but zero, the enemy can''t be seen.

2) 360 degree viewing
This lets the entity look in any direction it likes. because you''re using axis aligned squares or boxes for the tiles, all you have to do is create a line from A (entity position) to B (viewer position) and count how many boxes it intersects. the good thing is that you dont have to count all the intersections - as soon as you find 1 it means the object is hidden and the test can exit. Google "line box intersection" (there maybe something on this at www.magicsoftware.com too).

good luck!

Hey... I''d only have to check for intersection every 16/15 pixels...

Where can I find info on this "a-star" algorthim you speak of?

quote:

---

Original post by starstriker1
Hey... I''d only have to check for intersection every 16/15 pixels...

Where can I find info on this "a-star" algorthim you speak of?

---

http://www.geocities.com/jheyesjones/astar.html
http://theory.stanford.edu/~amitp/GameProgramming/
http://www.ccg.leeds.ac.uk/james/aStar/

were all found in seconds by using www.google.com .

To Everyone:

It seems like every week, or every couple of days, there is a request like the above, from someone who does not seem to know how to use google to get answers to basic questions.

I''m wondering if maybe GameDev should put up some really large banner on the front page of all forums, saying "Google before you ask!" to help people learn to use google to get quick and accurate answers to their questions?

Eric

that would be like expecting people to read the forum FAQ before they post...

I''ve just been ignoring posts like these recently tbh.

---

ai-junkie.com

quote:

---

Original post by fup
I''ve just been ignoring posts like these recently tbh.

---

ai-junkie.com

---

That''s probably the best strategy, fup. I''m just such an old softy that I feel sorry for the poster and hope they can see how easy it is and faster it is to get the answers to their questions using google, that I respond.

Eric

I used to be the same too Geta, but I''ve grown hard and calloused these last few months. There can be no excuses for not knowing about Google (or similar). I even caught one of my cats logging on to Google last week...

---

ai-junkie.com

/me cowers

I'll try to use a search engine first, in the future... sorry...

...!

Wow. I was just bashed for being a noobie! Its been a while... ah... memories...

Now, excuse me while I waddle out of the room in shame.




[edited by - starstriker1 on February 17, 2003 11:46:27 AM]

You weren''t being bashed for being a newbie. You were being bashed for not using your initiative.

---

ai-junkie.com

Actually there isn't a FAQ for this forum... and that's partly my fault. I offered to do one about 18 months ago but I got so bogged down with my thesis back then that I never got it done. Now of course I'm bogged down with a job and a bub on the way, so I doubt I will get it done (at least, not by myself).

If anyone wants to help out with getting a FAQ up, drop me a line. There's a button above to do that!

Cheers,

Timkin

[edited by - Timkin on February 17, 2003 6:18:22 PM]

quote:

---

Original post by Anonymous Poster
If everyone used google, we would have no use for these forums. Aside from getting opinions about a game idea.

---

I disagreed. You suggest that the forum''s usage is limited to opinion expression and answering questions. I think it is more than that. Also, I believe if more people used google before actually asking basic questions then I would suggest that we would enjoy a higher level of discussions , since people would be better informed on the basics. Not to mention, they would get answers to their questions MUCH faster by using google, than waiting for someone knowledgeable to drop by and help them.

Eric

quote:

---

Original post by starstriker1
/me cowers

I''ll try to use a search engine first, in the future... sorry...

...!

Wow. I was just bashed for being a noobie! Its been a while... ah... memories...

Now, excuse me while I waddle out of the room in shame.




[edited by - starstriker1 on February 17, 2003 11:46:27 AM]

---

No one''s trying to bash you. At least not me. Your request just demonstrated what has become (over the months and years) a very obvious problem. That is, that so many people don''t know about google, and what it can be used for.

Don''t take it personal ok?

Eric

I didn''t.

I just like to have a little fun when I''ve made a mistake, rather than sit in a corner and wimper! :D

Ok, I searched around a bit on google, and I found a bit on the A* Algorithim. I get the basics... the algorithim assigns each tile a value, which increases the farther it goes on. When the wanted end point is found, the algorthim traces back, always going back through tiles with the lowest values. Wow. I learned so much, my head is going to explode! Well... not really...

I''m stumped as to how to use the algorithim... use it for every cycle on every AI? That could get laggy. Should I use it once every so often, and every time, update an internal list of coordinats for a path?

And how does the algorithim search out the target? Seeing the java demo that Geta provided by link, I saw how it went iteration by iteration, creating a bigger set of data. How does it go about this? The tutorials I found on the net were... cryptic, to say the least (by way of tens of pages of discussion...). Could someone explain to me how to implement this properly?

quote:

---

Original post by starstriker1
Ok, I searched around a bit on google, and I found a bit on the A* Algorithim. I get the basics... the algorithim assigns each tile a value, which increases the farther it goes on.

When the wanted end point is found, the algorthim traces back, always going back through tiles with the lowest values.

---

AFAIK, A* can be set up to work either way, lowest or highest, depending on your application.

quote:

---

I''m stumped as to how to use the algorithim... use it for every cycle on every AI? That could get laggy. Should I use it once every so often, and every time, update an internal list of coordinats for a path?

---

That all depends. How is your game architected? What are you using the A* for? In a threaded game, the A* search could be in a thread all its own and so cycles are irrelevent. In a non-threaded game, the representation of the search space (the world or whatever graph you are searching) could be small enough that an optimized A* could search it within a single cycle. And it is quite possible to implement A* as a search across game cycles.

quote:

---

And how does the algorithim search out the target? Seeing the java demo that Geta provided by link, I saw how it went iteration by iteration, creating a bigger set of data. How does it go about this? The tutorials I found on the net were... cryptic, to say the least (by way of tens of pages of discussion...). Could someone explain to me how to implement this properly?

---

A* uses a heuristic to guide its search. The better the heuristic (ie. the closer it is to actual) then the better A* searchs. Even with a poor heuristic, the A* will at least find a solution.

Since its only been a few days, I would wonder if all "tens of pages of discussion" were read and understood? There is no fast or cook-book approach to learning this stuff. It takes time, and implementation and experimentation.

Did you work entirely through Justin''s tutorial?

Eric

Probably not. I''ll look over the links you provided again...