2
\$\begingroup\$

My game's map format uses a bunch of triangles to make up the platforms and terrain in 2d. Right now I can set up a 2d array of nodes for the A* (A star) algorithm that basically is a bunch of rectangles across the maps x and y that can be set to "wall" if the A* algorithm should try to go around it.

However I want a function in the map loader to create the node overlay if the nodes are not specified. I was thinking if more than n percent of the A* rectangle overlaid on map was filled by polygons I could mark that entry in the array as "wall". However I'm stuck on how to do this (or even start) where/when the triangles can be overlapping and also of variable size.

Improve this question
\$\endgroup\$
1
\$\begingroup\$

You're starting with an image, and trying to overlay pathfinding information onto that. Generally this would be approached in one of the following ways

  • Create a background image, then use XML, JSON or some other file-based data format to create the metadata, by hand. This is trial and error, since you have to guess the positions and then test, guess and then test, ad nauseum.

  • Create a background image, then use a custom tool to then array an A* node map over this. If you can't find the tool, you'll need to make one. This is easier than writing this into a file as raw data, by hand. I would just put a different mode into the game engine that allows you to load a map and click to create and join up map nodes over this, and then save this out to file. This is ultimately why many games have editors built in, that you can access from the menu -- it was for the developers' convenience. This, in your case, is probably the most sensible approach.

  • Generate image map at same time A* graph; this is a purely procedural approach and only useful if you are generating only random levels. The idea here is that the topology (connectedness i.e. A* map) of the level is generated, and then from that, the background image is generated. Of course, this takes control of the art out of the hands of developer and artists, to some degree.

You can try to do it procedurally, it's going to be substantially more difficult though. If you are adamant about going down this route, obviously your approach has to be based on pixel colours, and so you may need to generate a secondary image that is used purely for A* pathing determination.

Improve this answer
\$\endgroup\$
  • \$\begingroup\$ Wow thanks for the reply. See, the reason I need the function is I have a scripting engine which can create new polygons which could be used in turn for procedurally generated levels whereas I would want to call the recalculateAStarMapNodes() or what have you simply for convenience in scripts. The regular levels I can do by hand(have builtineditor). By image do you mean(this is my interpretation) create a 2d bool array which has detail for map and then draw the triangles to this array then blockerize(?word) this to create the nodes? This could work fairly well, I'll mark it answered now,thanks \$\endgroup\$ – jett Nov 12 '11 at 14:25
  • \$\begingroup\$ No problem. Yeah, image = 2D array. What I meant by the image thing was, given your polygon map which consists of space and solids, rasterise(!) these into eg. a black and white image / 2D bool array representing your A* tiles (blocked vs. open). The reason I mentioned a secondary image is I wasn't sure if your background art was drawn first, and then had to be processed in order to assign a map over that. In that case you'd need a "cleaner" version of the background image, which your A* map generator could work with easily in order to create the pathfinding map. \$\endgroup\$ – Engineer Nov 12 '11 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.