tag:blogger.com,1999:blog-5052387.post5398234129535491217..comments2024-03-17T16:13:55.262-07:00Comments on Blobs in Games: Updating my Introduction to A*Amithttp://www.blogger.com/profile/12159325271882018300noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-5052387.post-49501934938772564312016-03-04T06:37:07.895-08:002016-03-04T06:37:07.895-08:00Not at all! It's *not* obvious, and my diagram...Not at all! It's *not* obvious, and my diagrams don't make it completely clear. :(<br /><br />What A* sees is the abstract "graph" data -- nodes and the connections ("edges") between nodes. It doesn't actually know that the nodes represent polygons, or that the nodes "mean" a location on a map. To graph search (including A*), the nodes could be anything. For example, you might make nodes for moods like "happy" and "sad", and then you could have an edge from sad-->happy that is labeled "eat ice cream". Then if you ask graph search how to get from "sad" to "happy" it would say the shortest path is to eat ice cream. Graph search is quite useful for lots of things.<br /><br />For game maps we use places for nodes. What A* needs to know is what the possible places are and what's connected to what. So we could use a polygon for each graph node, and then adjacent polygons (you can walk from one to the other) would get a graph edge. Or we could use a grid coordinate for each graph node, and then adjacent grid tiles would get a graph edge.<br /><br />The way the graphs are drawn in the visualizations is mostly separate, and not something A* actually sees.<br /><br />(This brings up another topic I should add to the page — when people say A* finds the "shortest" or "optimal" path, that's only on the *graph* and not necessarily the shortest path on the map! Another topic…)<br />Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-1498686492622725502016-03-04T00:28:38.054-08:002016-03-04T00:28:38.054-08:00Then how are the polygons used for pathfinding? So...Then how are the polygons used for pathfinding? Sorry if the question seems too basic, I am guessing you probably wrote about this somewhere.MGhttps://www.blogger.com/profile/10379318968029633048noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-56765334637079318142016-03-03T09:57:59.402-08:002016-03-03T09:57:59.402-08:00The abstract graph structure doesn't actually ...The abstract graph structure doesn't actually have a location inside the polygon. The polygon itself is the node. For the visualizations on the page, I pick a point manually, but A* doesn't actually see that.Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-91032443798568267952016-03-03T03:35:03.437-08:002016-03-03T03:35:03.437-08:00How do you determine the points inside the polygon...How do you determine the points inside the polygons? Manually?MGhttps://www.blogger.com/profile/10379318968029633048noreply@blogger.com