How to draw province borders

I'm making an AoH2-like strategy game. I have a provinces.bmp image where each province has a unique color. The border coordinates are currently extracted by looping through pixels and checking neighbors. How can I draw the borders and fill the provinces with color? Also, is there a better way to extract border coords?
fn draw_borders(mut commands: Commands) {
let img =
image::open("assets/maps/testmap/provinces.bmp").expect("Failed to open provinces.bmp");
let (width, height) = img.dimensions();

let mut pixels: Vec<(u8, u8, u8)> = Vec::with_capacity((width * height) as usize);
for (_, _, pixel) in img.pixels() {
    pixels.push((pixel[0], pixel[1], pixel[2]))
}

let mut border_coords = Vec::new();
for y in 0..height {
    for x in 0..width {
        let current = pixels[(y * width + y) as usize];

        let neighbors = [
            (x.saturating_sub(1), y),
            ((x + 1).min(width - 1), y),
            (x, y.saturating_sub(1)),
            (x, (y + 1).min(height - 1)),
        ];

        for &(nx, ny) in neighbors.iter() {
            if pixels[(ny * width + nx) as usize] != current {
                border_coords.push((x, y));
                break;
            }
        }
    }
}

let border_coords: HashSet<_> = border_coords.into_iter().collect(); // remove duplicates
// render borders

}

Comments

[Hugo Abranches]

You’re essentially trying to extract province borders from a province-color map and then render borders/fill areas.

⸻

1️⃣ Problems in your current code
• There’s a bug in this line:

let current = pixels[(y * width + y) as usize];

It should be:

let current = pixels[(y * width + x) as usize];

Otherwise you’re reading the wrong pixel.
• Checking just 4 neighbors (N, S, E, W) works but can be slow and sometimes gives jagged borders.
• Using a Vec and then converting to HashSet works, but using HashSet from the start can save memory/duplicates.

⸻

2️⃣ Better way to extract borders

Instead of checking each neighbor manually, you can use a marching squares / contour tracing algorithm, like OpenCV’s findContours. That gives you ordered border coordinates (useful if you want smooth outlines or polygon shapes for rendering).

If you want to stick to pure Rust without OpenCV:
• Use a flood-fill to group provinces by color.
• Once you have a province’s pixels, you can compute the border as the set of pixels that have a neighbor outside the province (like you’re doing now, but only within the province).
• This avoids checking every pixel against every neighbor blindly.

Rough pseudo-code:

fn find_province_borders(pixels: &[(u8,u8,u8)], width: u32, height: u32) -> HashMap<(u8,u8,u8), Vec<(u32,u32)>> {
    let mut borders = HashMap::new();
    let mut visited = vec![false; (width * height) as usize];

    for y in 0..height {
        for x in 0..width {
            let idx = (y * width + x) as usize;
            if visited[idx] { continue; }

            let color = pixels[idx];
            let mut stack = vec![(x, y)];
            let mut province_pixels = Vec::new();

            while let Some((px, py)) = stack.pop() {
                let i = (py * width + px) as usize;
                if visited[i] { continue; }
                if pixels[i] != color { continue; }

                visited[i] = true;
                province_pixels.push((px, py));

                for &(nx, ny) in &[
                    (px.saturating_sub(1), py),
                    ((px + 1).min(width-1), py),
                    (px, py.saturating_sub(1)),
                    (px, (py + 1).min(height-1))
                ] {
                    stack.push((nx, ny));
                }
            }

            // find borders within province
            let mut province_border = Vec::new();
            for &(px, py) in &province_pixels {
                for &(nx, ny) in &[
                    (px.saturating_sub(1), py),
                    ((px + 1).min(width-1), py),
                    (px, py.saturating_sub(1)),
                    (px, (py + 1).min(height-1))
                ] {
                    let ni = (ny * width + nx) as usize;
                    if pixels[ni] != color {
                        province_border.push((px, py));
                        break;
                    }
                }
            }

            borders.insert(color, province_border);
        }
    }

    borders
}

This approach groups provinces first, which is more efficient than checking neighbors globally, especially for large maps.

⸻

3️⃣ Drawing borders and filling provinces

Assuming you’re using Bevy or a similar ECS/2D renderer:
• Fill provinces:
Iterate over each province’s pixels and spawn quads (or a texture atlas). For performance, it’s better to generate a single mesh per province rather than one quad per pixel. Using bevy_prototype_lyon is perfect for this:

use bevy_prototype_lyon::prelude::*;

for (color, border_coords) in borders.iter() {
    // create a polygon for the province
    let points: Vec<Vec2> = border_coords.iter()
        .map(|&(x, y)| Vec2::new(x as f32, y as f32))
        .collect();

    let shape = shapes::Polygon {
        points,
        closed: true,
    };

    commands.spawn(GeometryBuilder::build_as(
        &shape,
        DrawMode::Fill(FillMode::color(Color::rgb_u8(color.0, color.1, color.2))),
        Transform::default(),
    ));

    // optionally, draw border
    commands.spawn(GeometryBuilder::build_as(
        &shape,
        DrawMode::Stroke(StrokeMode::new(Color::BLACK, 1.0)),
        Transform::default(),
    ));
}

• Border thickness: Adjust StrokeMode thickness.
• Filling: The fill is automatically done by FillMode::color.

Note: The pixel coordinates might need Y-flip depending on your renderer (images usually have origin top-left, Bevy’s coordinate system is bottom-left).

⸻

4️⃣ Optional optimization
• If your province shapes are large, vectorize borders using Marching Squares or raster_to_polygon algorithms.
• This reduces the number of points needed and makes the rendering faster.