• Advertisement
Sign in to follow this  

map-format / pathfinding

This topic is 2999 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there, im Pasqual aka bloodstix and i'm just creating my first post in a forum i read over a long time now :) Im 23years young and im writing in various programming languages since the age of 13 or 14. 1 year ago i slowly started programming on in my first little 2D-RTS game. Waypoints are simple 1. Some little "parts" of an engine (log/conf-reader, sdl/opengl initialization, texture-manager, game-manager, game-state factory, input class, and such stuff) in a very basic way, but enough for this game to work :) // Status DONE 2. Display a custome sized map of colored tiles (48x48pixel) in plain 2D (non isometric) from static array and implement vertical horizontal scrolling with min/max scroll values. // Status DONE So i didnt test it with textures and alpha-blending yet 'cuz im to uncreative to draw some tiles with paint ( xD ), but brown/green/red colored tiles are ok for now :D 3. Getting a map-format done which is quite flexible and ascii-text for first // TODO (Need feedback, look next code quotation) 4. Get an Soldier for each player which can move over the map by select-point-and-click of the player (npc Soldier does nothing first :) ai is a complex thing on its own) // TODO So you see im making little steps forward. The problem is not that im not able to create a map format, but i would like to know from some experienced guys which pros and cons are for my map format. So here is a little example of a map-file:
;; title is the levels name like "Frost incomming"

;; width and height are in tiles

;; tilesize is width and height of tiles in pixel

;; res_x and res_y are screen-resolution the map and tiles
;; are made for, so to say an "optimal viewed in.." option :)

;; scrollvelocity in tiles, scroll how many 
;; tiles per ATM right/left/up/down keypresses 

;; humans is a subsection of map_params and a counter in same time
;; defines how many humans can play on this map

;; id is subsection of humans defining some starting-values 
;; for each player and maybe the color and team-mates
;; ki is same for npc players (i'm german)
{ map_params 
	title=Level 1
	width=3
	height=3
	tilesize=48
	res_x=1024
	res_y=786
	scrollvelocity=1
	{ humans=1
		{ id=1
			color=0
		}
	}
	{ ki=1
		{ id=1
			color=1
	}	}
}

;; here comes the definition of the textures used for this map
;; and their id's
{ textures 
	1=grass.jpg
	2=player.jpg
}

;; tile definition starts now...
;; type is set to 0 here so its a grass-type tile
;; textures speaks for it self i think, multiple textures can be
;; defined which are then overblended in top to bottom order
{ tile=1
	type=0
	{ textures=1
		id=1
	}
}
{ tile=2
	type=0
	{ textures=
		id=1
	}
}
{ tile=3
	type=grass
	{ textures=
		id=1
	}
}
{ tile=4
	type=grass
	{ textures=
		id=1
	}
}
{ tile=5
	type=grass
	{ textures=
		id=1
	}
}
{ tile=6
	type=grass
	{ textures=
		id=1
	}
}
{ tile=7
	type=grass
	{ textures=
		id=1
	}
}
{ tile=8
	type=grass
	{ textures=
		id=1
	}
}
{ tile=9
	type=grass
	{ textures=
		id=1
	}
}

;; unit definition
;; type 0 = soldier (1 unit)
;; position is the tile it stands on,

;;tile-specifications in map-file make them be placed in middle of the tile
{ unit=1
	type=0
	position=1
	ownerid=1
}
;{ building=1
;	type=fort
;	position=4
;	ownertype=player
;	ownerid=1
;}
On loading a level, the entire file will be read into a stl-vector and is going to be parsed then. Please let me know what u think is good and what isn't. Maybe you are missing something essential. And can you give me some advice on path-finding methods for this kind of game? I don't think that iterating through all tiles again and again and check if the tile is walkable is the most efficient method. kindly, bloodstix [Edited by - bloodstix on December 8, 2009 3:59:33 PM]

Share this post


Link to post
Share on other sites
Advertisement
oh, i thought at least 1 or two persons could gimmeh some feedback.
hope someone will look into this and reply :(

Share this post


Link to post
Share on other sites
Looks alright, I did something similar once but used XML instead.

There is some redundancy on the tile definition part, maybe you could save some space when a tile repeats itself by storing the number of times it is repeated instead of repeating the same data over and over.

Share this post


Link to post
Share on other sites
As Kwizatz already noted, the tile data section contains redundant data. I see there's a texture list - good - but how about storing a tile type list instead? Then you only need to store a single index into that list for every tile, and for each tile type you only need to store it's properties once.

Either way, it's smart to keep things simple first - a text-based format is easier to debug and to modify than a binary one. You can always replace it with a binary format later. Personally, I would write a conversion tool at some point, that can translate the text version into the binary version (and perhaps the other way around as well). I've used Python for that in the past, which worked really (combined with PIL and Pygame it also makes for good data previewers and editors).


As for pathfinding, look up on A*. Checking whether or not a tile is solid shouldn't be too heavy - a single lookup in an array of sorts - and once you've got a route, you can keep following it (perhaps checking it every now and then and finding a new path if the old one is obstructed). For simple obstacles, some avoidance behaviour that gets out of the way and then picks up the old path again may work well enough.

Share this post


Link to post
Share on other sites
Oh thanks for at least some replys :D

You are right, the tiles in this example are redundant. In later maps there will be mostly different tiles. As you see, each tile got an array of textures, so they will be layered. Tile type is more like, trigger,passable,capture point, ....and thats defined ingame :)

So for the A*: I would calculate the whole move in 1 frame in a while loop and store the path of tile-id's in an array which then is read every frame and the unit going to be moved in its movespeed ?

What things else do i have to take care off when i start writing the map in binary format than switching file-io-mode to binary?

Thanks in advance
bloody

Share this post


Link to post
Share on other sites
Quote:
Original post by bloodstix
Tile type is more like, trigger,passable,capture point, ....and thats defined ingame :)

Are you sure you want to make 'trigger' and 'capture point' tile properties instead of separate objects? Depends a bit on how you're going to use those, but if the number of triggers and capture points is low compared to the number of tiles, you may be better off creating separate objects for those (with the added benefit that triggers can overlap each other, things like that).

Quote:
So for the A*: I would calculate the whole move in 1 frame in a while loop and store the path of tile-id's in an array which then is read every frame and the unit going to be moved in its movespeed ?

You may want to store a movement cost per tile, if tile types are going to affect movement. That should then be taken into account by the pathfinding algorithm. Either way, yes, you'd store that path for the unit to use. I wouldn't use an array for that, rather a std container class, perhaps encapsulated into a PathInfo class or something, but yeah.

Quote:
What things else do i have to take care off when i start writing the map in binary format than switching file-io-mode to binary?

The only things that come to mind are to pick the right data type sizes (e.g. if you plan on using more than 256 textures per map, a single byte isn't going to work as a texture list index). That, and laying out data so that it can be read into memory directly (keep padding in mind!). Likely not a big issue, but it'll speed things up a little. You may want to look into Google protobuf, bytheway. I (still) haven't used it, but it allows for language-independent object definitions and code-generation for C++, Java and Python, as well as xml output.

Share this post


Link to post
Share on other sites
Hi there again ^^

I read the article about A* now but i think it is inefficient in one way, if im not wrong?
If i select a unit with my mouse and scroll the map and point on another square or enemy on the other side of the map, i do know the target X and Y.
The A* doesnt use the target coordinates if i am not totaly wrong?

I thought about pathfinding a bit and i came to this "semi" solution:

1. Check the direction the target is in by getting X,Y of the tile the mouse clicked in.
if(target.x > this.x) direction |= LEFT;
if(target.y > this.y) direction |= TOP;

2. Check tile after tile in this direction if passable ...

Wouldn't this be faster?


Thanks in advance
~bloody

Share this post


Link to post
Share on other sites
Quote:
Original post by bloodstix
The A* doesnt use the target coordinates if i am not totaly wrong?
You are totally wrong.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement