Jump to content
  • Advertisement
povilaslt2

2D Sidescroller pathfinding using A*(A star) algorithm

Recommended Posts

Hello, I'm trying to implement enemy pathfinding algorihtm, but i have problem with empty tile collision when moving enemy to node.

 

For example this image shows how it should move like shown in example:

large.emptyExample.png.7ca087fc95ef0becf2248a02950b9c48.png

But it stucks at last tile:
large.stuckExample.png.7816d520acf3f66d71bab023f6d714eb.png

 

It happens because enemy collides with right side of "air" tile and then it removes from node list because it "collided", but it works with not "air" tiles of course. How do fix this problem?

Code:

void Enemy::generateMoveToNode(AStar::Vec2i lastNode)
	{
		auto lastSave = AStar::Vec2i{ 0.0f, 0.0f };

		while (!target.empty())
		{
			if (target.back().y == lastNode.y)
			{
				lastSave = target.back();
				target.pop_back();
			}
			else
			{
				moveToNodes.push_back(lastSave);
				moveToNodes.push_back(target.back());
				generateMoveToNode(target.back());
				return;
			}
		}

		moveToNodes.push_back(lastSave);
	}

	void Enemy::updateTarget(std::shared_ptr<InputManager> inputManager)
	{
		if (moveToNodes.empty()) return;

		// Calculate half sizes.
		float halfWidthA = getSize(0) / 2.0f;
		float halfHeightA = getSize(1) / 2.0f;
		float halfWidthB = 32.0f / 2.0f;
		float halfHeightB = 32.0f / 2.0f;

		// Calculate centers.
		auto centerA = glm::vec2(getPosition(0) + halfWidthA, getPosition(1) + halfHeightA);
		auto centerB = glm::vec2((moveToNodes.front().x * 32.0f) + halfWidthB, (moveToNodes.front().y * 32.0f) + halfHeightB);

		// Calculate current and minimum-non-intersecting distances between centers.
		float distanceX = centerA.x - centerB.x;
		float distanceY = centerA.y - centerB.y;
		float minDistanceX = halfWidthA + halfWidthB;
		float minDistanceY = halfHeightA + halfHeightB;

		setKey(inputManager->getKeyBinding("Move Left"), false);
		setKey(inputManager->getKeyBinding("Move Right"), false);
		setKey(inputManager->getKeyBinding("Jump"), false);
		setKey(inputManager->getKeyBinding("Duck"), false);

		// If we are not intersecting at all, return (0, 0).
		if (abs(distanceX) >= minDistanceX || abs(distanceY) >= minDistanceY)
		{
			if (moveToNodes.front().y > ceil(getPosition(1) / 32.0f))
				setKey(inputManager->getKeyBinding("Jump"), true);
			else if (moveToNodes.front().y < ceil(getPosition(1) / 32.0f))
			{
				if (getCanClimb())
					setKey(inputManager->getKeyBinding("Duck"), true);
			}
			else
			{
				if (moveToNodes.front().x < ceil(getPosition(0) / 32.0f))
					setKey(inputManager->getKeyBinding("Move Left"), true);
				else if (moveToNodes.front().x > floor(getPosition(0) / 32.0f))
					setKey(inputManager->getKeyBinding("Move Right"), true);
			}

			updateInput(inputManager);
			return;
		}

		// Calculate and return intersection depths.
		float depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX;
		float depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY;

		updateInput(inputManager);
		moveToNodes.erase(moveToNodes.begin());
	}

generateMoveToNode: recursive function to generate all nodes.

updateTarget: updates enemy every frame to check if it hits node and then removes it from list and checks next till no nodes left.

Edited by povilaslt2

Share this post


Link to post
Share on other sites
Advertisement

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
  • Advertisement
  • Popular Tags

  • Similar Content

    • By Custom GameArt
      Developing a game? Don't want to make art yourself or hire expensive professional artists to do it? We've got you covered. Our artists will create custom 2D sprites and animations for the lowest prices.
      Visit https://www.CustomGameArt.com today for 40% Off.
      We make custom 2D video game graphics and animations of any kind in any style. We create pixel art for mobile games, pc games, avatars, gifts, music videos, any personal requests, and anything else. If you need tons of graphics, contact us on our website or at OfficialCGA@gmail.com for special promotions and bundle deals for game developers.

    • By Luke McManus
      Hey all,

      So I have this unfathomable obsession with the games LIMBO and INSIDE, two games produced by Playdead Studios. But as a sound designer, I'm specifically into the audio of the game, its use of ambient tracks and specific sounds to create this level of emotion I've never felt in a platformer before.

      I took a stab at redesigning the sound and ambiance of one of LIMBO's trailers to see if I could replicate such emotionality with my own creativity. Check it out below. All feedback is appreciated. 
      https://www.youtube.com/watch?v=-LgHHBtAWwE
      Thanks!
    • By RoKabium Games
      Been a bit quiet recently, but we've been busy bug fixing and tweaking things... Now we have lots more 'Particle effects' in the game, specifically here the Flamethrower and Enemy attacks!
    • By nilkun
      Hello everyone!
      First time posting in the forum.
      I've just completed my first game ever ( C++ / SDL ), and I am feeling utterly proud. It is a small game resembling Missile Command. The code is a mess, but it is my mess! In the process of making the game, I developed my own little game engine.
      My question is, where would be a good place to spread the news to at least get some people to try the game?
    • By owenjr
      Hi, I'm a Multimedia Engineering student. I am about to finish my dergree and I'm already thinking about what topic to cover in my final college project.
      I'm interested in the procedural animation with c++ and OpenGL of creatures, something like a spider for example. Can someone tell me what are the issues I should investigate to carry it out? I understand that it has some dependence on artificial intelligence but I do not know to what extent. Can someone help me to find information about it? Thank you very much.
       
      Examples: 
      - Procedural multi-legged walking animation
      - Procedural Locomotion of Multi-Legged Characters in Dynamic Environments
    • By MarcusAseth
      Hi guys, I'm having a problem rendering with DWrite, and I don't understand why, can you help me figure it out?
      As you can see in the image below, if you look carefully you'll notice that the top of R8 is cut (missing 1 row of pixels), the bottom of R11 is cut again, the 4 in R14 is rendered weird compared to the 4 in R4 and so on, if you look closely you'll spot more yourself.
      I can't figure out why 😕
      Under the image I'll also leave the code, in case I'm doing something wrong like with type conversion or stuff. Any help is much appreciated

      #include "GBAEmulator_PCH.h" #include "Disassembler.h" #include "GBAEmulator.h" Disassembler::Disassembler(LONG width, LONG height, HINSTANCE hInstance, GBAEmulator* emuInstance) : D2DWindowBase(width, height, hInstance, emuInstance), m_background(0.156f, 0.087f, 0.16f, 1.f), m_textFormat{ nullptr } { //Init Window std::string className = "Disassembler"; std::string windowName = "Disassembler"; WNDCLASSEX clientClass{}; clientClass.cbSize = sizeof(WNDCLASSEX); clientClass.style = CS_HREDRAW | CS_VREDRAW; clientClass.lpfnWndProc = GBAEmulator::DisassemblerWinProc; clientClass.hInstance = m_hInstance; //clientClass.hIcon =; TODO: Add Icon clientClass.hCursor = LoadCursor(m_hInstance, IDC_ARROW); clientClass.hbrBackground = (HBRUSH)(COLOR_BACKGROUND + 1); clientClass.lpszClassName = className.c_str(); //clientClass.hIconSm =; TODO: Add Icon DWORD windowStyle = WS_VISIBLE | WS_CAPTION | WS_MINIMIZEBOX | WS_TABSTOP | WS_SYSMENU; m_isValid = InitWindow(windowName, clientClass, windowStyle, false); //Init DWrite if (m_isValid) m_isValid = InitDWrite(); std::vector<std::wstring> tempEntries{ L"PC: ", L"R0: ", L"R1: ", L"R2: ", L"R3: ", L"R4: ", L"R5: ", L"R6: ", L"R7: ", L"R8: ", L"R9: ", L"R10: ", L"R11: ", L"R12: ", L"R13: ", L"R14: ", L"R15: ", L"R16: " }; std::wstring value = L"-UNDEFINED-"; FLOAT left{}, top{}, right{ 300.f }, bottom{ 50.f }; for (auto& s : tempEntries) { m_entries.emplace_back(TextEntry{ s, value, D2D1_RECT_F{ left, top, right, bottom} }); top += 30.f; bottom += 30.f; } } bool Disassembler::InitDWrite() { //Set Text Format HRESULT hr; hr = m_DWriteFactory->CreateTextFormat( L"consolas", NULL, DWRITE_FONT_WEIGHT_NORMAL, DWRITE_FONT_STYLE_NORMAL, DWRITE_FONT_STRETCH_NORMAL, 22.f, L"en-US", &m_textFormat ); if (FAILED(hr)) { MessageBox(NULL, "Failed to create TextFormat", "Error", MB_OK); return false; } //Set Colors m_renderTarget->CreateSolidColorBrush( D2D1::ColorF(D2D1::ColorF::SkyBlue), &m_fillBrush1 ); m_renderTarget->CreateSolidColorBrush( D2D1::ColorF(D2D1::ColorF::Crimson), &m_fillBrush2 ); return true; } Disassembler::~Disassembler() { DestroyWindow(m_hwnd); if (m_textFormat) m_textFormat->Release(); if (m_fillBrush1) m_fillBrush1->Release(); if (m_fillBrush2) m_fillBrush2->Release(); } void Disassembler::Updade(float deltaTime) { } void Disassembler::Draw() { m_renderTarget->BeginDraw(); m_renderTarget->Clear(m_background); for (auto& entry : m_entries) { DrawEntryWithShadow(entry); } m_renderTarget->EndDraw(); } void Disassembler::DrawEntryWithShadow(const TextEntry& entry) { //shadow offset D2D1_RECT_F shadowPos = entry.position; shadowPos.top += 1.05f; shadowPos.left -= 0.95f; //draw text DrawEntry(entry.text, shadowPos, m_fillBrush2); DrawEntry(entry.text, entry.position, m_fillBrush1); D2D1_RECT_F valuePos = entry.position; FLOAT valueOffset = 50.f; valuePos.left += valueOffset; valuePos.right += valueOffset; shadowPos.left += valueOffset; shadowPos.right += valueOffset; //draw value DrawEntry(entry.value, shadowPos, m_fillBrush2); DrawEntry(entry.value, valuePos, m_fillBrush1); } void Disassembler::DrawEntry(const std::wstring& text, const D2D1_RECT_F& pos, ID2D1SolidColorBrush* brush) { m_renderTarget->DrawTextA( text.c_str(), static_cast<UINT>(text.size()), m_textFormat, pos, brush, D2D1_DRAW_TEXT_OPTIONS_NONE ); }  
    • By Catalin Danciu
      Hello,
      In the hopes that my thread is not off-topic or offensive in any way, I dare to ask the following "noob" question:
      what would be the correct way to create sprite animations from 2D *.bmp files?
      I have for reference the 2001 game  Desperados:Wanted Dead or Alive.
      with the help of some tools i found , I was able to extract files containing what seems to be animation frames and frame shadow masks for animating a horse.
      Attached are the archived assets.
      My goal is to recreate the demo level of the game using Unity, for educational purposes.
      I have started by loading the background map layer (also a large bmp file), and next step is to load a 2d character object and animate on the perspective.
       
      Horse_Brown.rar
    • By Alberto Muratore
      Hello, my name is Alberto Muratore and I'm a young game developer specialized in programming.

      Last summer I finished working on Abstract Arena, my first completed project published on Steam. During the development, lasted more than 1 year, I created every aspect of the game except for the audio sector. I previoulsy joined small competitions and had collaborations within the amateur scene, since I started having fun with game development when I was a kid. In the recent months I also started writing videogames reviews for a english-italian website about indie games.

      Abstract Arena Steam page: http://store.steampowered.com/app/678230/Abstract_Arena/
      Abstract Arena website: http://www.abstractarena.com/

          

      I'm currently offering my skills as freelancer in the role of programmer: what I'm searching for is a project that only lacks of the coding part. I'm very good at using the GameMaker: Studio engine, and I already own a license to export on Android platform. I can write code for any genre of 2D games, and I already have experience with the peculiarities of the Android platform (multiple touch controls, accelerometer). I will be able to start working full time only during September, so be aware of that.

      The plan is the following:
      1 - you have an idea about your next project (2D game of any kind, for Windows and/or Android platform),
      2 - you (or your team) create all of the graphics and audio resources,
      3 - I write the whole code for the game (gameplay, menus and anything within the game) putting everything togheter [during September],
      4 - if you like my work you can choose how much to pay for it, and you (or your team) keep the rights to sell the game without sharing any percentage with me.

      Thank you for reading my announcement
      If you have any question, please write me at the following address: albertomurat@gmail.com
    • By Andrew Parkes
      I am a talented 2D/3D artist with 3 years animation working experience and a Degree in Illustration and Animation. I have won a world-wide art competition hosted by SFX magazine and am looking to develop a survival game. I have some knowledge of C sharp and have notes for a survival based game with flexible storyline and PVP. Looking for developers to team up with. I can create models, animations and artwork and I have beginner knowledge of C sharp with Unity. The idea is Inventory menu based gameplay and is inspired by games like DAYZ.
      Here is some early sci-fi concept art to give you an idea of the work level. Hope to work with like minded people and create something special. email me andrewparkesanim@gmail.com.
      Developers who share the same passion please contact me, or if you have a similar project and want me to join your team email me. 
      Many thanks, Andrew.

    • By mike44
      Hi
      saw in dependency walker that my app still needs msvcp140d.dll even after disabling debug.
      What did I forget in the VS2017 release settings? After setting to multithreaded dll I get linker errors.
      Thanks
       
  • Advertisement
  • Popular Now

  • Forum Statistics

    • Total Topics
      631395
    • Total Posts
      2999758
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!